pytudes._2021.miscellany.sorting.mergesort

Module Contents

Functions

_merge(left, right)
_mergesort(nums)	Complexity:
_mergesort_space_optimized(nums, start, end)	Performing merge operation in-place by overwriting associated indexes of input array
mergesort(nums[, in_place])	Complexity:

pytudes._2021.miscellany.sorting.mergesort._merge(left, right)

Parameters:

• left (list) –

• right (list) –

Return type:

list

pytudes._2021.miscellany.sorting.mergesort._mergesort(nums)

Complexity:

n = len(nums)

Space: 2n = O(n)

for (2 * n/2) copies of sorted left/right subarrays and (1 * n) copy of merged array

Examples:

>>> _mergesort([])
[]

Parameters:

nums (list) –

Return type:

list

pytudes._2021.miscellany.sorting.mergesort._mergesort_space_optimized(nums, start, end)

Performing merge operation in-place by overwriting associated indexes of input array

Complexity:

n = len(nums)

Space: n = O(n)

for (2 * n/2) copies of sorted left/right subarrays

Examples:

>>> _mergesort_space_optimized([], 0, 0)

Parameters:

• nums (list) –

• start (int) –

• end (int) –

Return type:

None

pytudes._2021.miscellany.sorting.mergesort.mergesort(nums, in_place=True)

Complexity:

n = len(nums)

Time: O(nlogn) Space: O(n) for copies of sorted subarrays

Examples:

>>> assert(mergesort([3,3,1,1,2,2], in_place=True) == mergesort([3,3,1,1,2,2], in_place=False))
>>> mergesort([3,3,1,1,2,2], in_place=True)
[1, 1, 2, 2, 3, 3]
>>> mergesort([3,2,1,1,2,3], in_place=True)
[1, 1, 2, 2, 3, 3]
>>> mergesort([0,-4,2,-2,4]*3, in_place=True)
[-4, -4, -4, -2, -2, -2, 0, 0, 0, 2, 2, 2, 4, 4, 4]

Parameters:

• nums (list) –

• in_place (bool) –

Return type:

list