DSA · Chapter 32 of 40
Merge Sort
Merge sort is a divide-and-conquer algorithm: split the array in half, sort each half recursively, then merge the two sorted halves in linear time. It is O(n log n) in every case and stable.
The cost is O(n) extra space for the merge step, which is why quick sort is often preferred in memory-constrained settings.
The merge step
Walk both halves with two pointers, always taking the smaller front element. Equal elements take from the left half first, which preserves stability.
Why log n levels
Halving the array repeatedly gives log n levels, and each level does O(n) merging work.
Example 1 (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:]
print(merge_sort([5, 3, 8, 1]))Output
[1, 3, 5, 8]Divide, sort, then merge.
Example 2 (python)
# merging two sorted lists is O(n)
print(sorted([1, 4] + [2, 3]))Output
[1, 2, 3, 4]The merge itself is a single linear pass.
Key points
- Merge sort is O(n log n) in best, average and worst case.
- It is stable but uses O(n) extra space.
- It is the standard choice for linked lists and external sorting.
- Divide and conquer gives log n levels of O(n) work.
💡 Note: Merge sort is preferred over quick sort when stability or guaranteed worst case matters.