Visualizer › Sorting
Merge Sort
Divide and conquer: split the array into halves, sort each half recursively, then merge the two sorted halves.
How it works
- Always O(n log n), whatever the input.
- Needs O(n) extra space for merging.
- Stable — the usual choice for sorting linked lists and for external sorting.
Complexity
- Best time: O(n log n)
- Average time: O(n log n)
- Worst time: O(n log n)
- Extra space: O(n)
- Stable: yes
Code (Python)
def merge_sort(a):
if len(a) <= 1:
return a
mid = len(a) // 2
left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
out, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
return out + left[i:] + right[j:]Practise: Recursion & Backtracking problems