Merge Sort
DSA · Sorting Algorithms
Theory
Merge sort is a divide-and-conquer algorithm: it splits the list in half, recursively sorts each half, then merges the two sorted halves by repeatedly taking the smaller front element. The recursion depth is log n and each level does O(n) merging work, so it always runs in O(n log n). It needs O(n) extra memory for merging and is stable.
Why we use it
It guarantees O(n log n) regardless of input order and is stable, which makes it reliable for large data and for sorting linked lists and external files.
When to use it
Use it when you need guaranteed performance, stability, sorting linked lists, or sorting data too large for memory (external merge sort).
How it works
- mergeSort(arr)
- Length <= 1? Yes: Return arr (already sorted). No: Split into left and right halves.
- Sort left half recursively
- Sort right half recursively
- Merge: repeatedly take the smaller front element
- Return merged sorted array
Syntax
merge_sort(arr):
if len(arr) <= 1: return arr
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
Time: O(n log n) always Space: O(n) StableExample
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
merged, i, j = [], 0, 0
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
merged += left[i:] + right[j:]
return merged
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))Key points
- Divide, sort halves, merge
- Always O(n log n)
- Stable but needs O(n) extra space
- Ideal for linked lists and external sorting