DSA Merge Sort
Merge sort recursively splits a list in half, sorts each half independently, and merges the two sorted halves back into one sorted list.
Divide and Conquer
Merge sort follows the classic divide-and-conquer pattern. It divides the list into two roughly equal halves, conquers each half by recursively sorting it, and combines the results with a merge step that walks through both sorted halves and interleaves them in order. The recursion bottoms out at lists of length zero or one, which are trivially sorted.
- Divide the list into two roughly equal halves.
- Recursively sort the left half.
- Recursively sort the right half.
- Merge the two sorted halves by repeatedly taking the smaller front element.
- Return the fully merged, sorted list.
Example
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))The Merge Step in Detail
The merge function never re-examines an element once it has been placed. It keeps two pointers, one into each sorted half, and always copies whichever pointed-to value is smaller into the result, advancing that pointer. Once one half runs out of elements, the remainder of the other half is copied over directly since it is already sorted.
Example
def merge_sort_verbose(arr, depth=0):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
print(' ' * depth + f'Splitting {arr}')
left = merge_sort_verbose(arr[:mid], depth + 1)
right = merge_sort_verbose(arr[mid:], depth + 1)
merged = merge(left, right)
print(' ' * depth + f'Merged {left} and {right} -> {merged}')
return merged
merge_sort_verbose([5, 2, 8, 1])Complexity Analysis
Example
def count_inversions(arr):
if len(arr) <= 1:
return arr, 0
mid = len(arr) // 2
left, left_inv = count_inversions(arr[:mid])
right, right_inv = count_inversions(arr[mid:])
merged = []
i = j = 0
inversions = left_inv + right_inv
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
inversions += len(left) - i
merged.extend(left[i:])
merged.extend(right[j:])
return merged, inversions
sorted_arr, total = count_inversions([2, 4, 1, 3, 5])
print(sorted_arr, total)Exercise: DSA Merge Sort
What are the two main phases of merge sort?
