MergeSort
Description
Recursively split the array into left and right halves until the array has one element. Begin merging these single element arrays into two element arrays, then four element arrays, etc, until you have your sorted array. During the merge process, ensure your forming a sorted array using a two pointers technique.
Complexity Analysis
Average case | \( O(nlogn) \) |
|---|---|
Best case | \( O(nlogn) \) |
Worst case | \( O(nlogn) \) |
Space Complexity | \( O(n) \) |
def mergeSort(arr):
if len(arr) > 1:
mid = len(arr) // 2
# Recursively break down the entire array by into left and right halves until they only contain one element
leftArr = mergeSort(arr[:mid])
rightArr = mergeSort(arr[mid:])
# Construct a sorted array by combining leftArr and rightArr with a two pointer algorithm
l = r = k = 0
while l < len(leftArr) and r < len(rightArr):
if leftArr[l] <= rightArr[r]:
arr[k] = leftArr[l]
l += 1
else:
arr[k] = rightArr[r]
r += 1
k += 1
# Copy remaining elements from leftArr, if any
while l < len(leftArr):
arr[k] = leftArr[l]
l += 1
k += 1
# Copy remaining elements from leftArr, if any
while r < len(rightArr):
arr[k] = rightArr[r]
r += 1
k += 1
return arr
return arrGeoffrey Lee