How Merge Sort Works
Merge sort halves the array until each piece is trivially sorted, then merges the pieces back together in order. O(n log n) on every input, stable, and the reason it needs a second array.
- Waiting
- Being compared
- Just moved
- In final position
Merge sort, 12 values in random order.
Counters
- Comparisons
- 0
- Writes
- 0
- n
- 12
- Average case
- O(n log n)
Settings
More options
Two to 48 numbers. Sorted in exactly the order you type them.
Merge sort
- 1
width = 1 - 2
while width < n: - 3
for lo in 0..n step 2*width: - 4
mid = lo + width - 5
hi = lo + 2*width - 6
// merge a[lo..mid) and a[mid..hi) - 7
take the smaller head each time - 8
width *= 2
The same array, every algorithm
Comparisons on the values above, cheapest first. Writes in the second line. Run it on nearly sorted values to see the O(n log n) sorts lose.
- Merge3344 writes
- Quick3340 writes
- Insertion4042 writes
- Shell4637 writes
- Heap5166 writes
- Bubble6062 writes
- Selection6618 writes
How the seven compare
| Algorithm | Best | Average | Worst | Extra memory | Stable |
|---|---|---|---|---|---|
| Bubble | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Insertion | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | No |
| Shell | O(n log n) | O(n√n) | O(n²) | O(1) | No |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
Scroll the table sideways for the rest of the columns.
Stable means equal values keep their original order.
Complexity
| Best | Average | Worst | Extra memory |
|---|---|---|---|
| O(n log n) | O(n log n) | O(n log n) | O(n) |
The O(n) buffer is the trade: an in-place merge exists but is slow enough in practice that nobody uses it.
How merge sort works
Merge sort splits the array in half, sorts each half the same way, and then merges the two sorted halves by repeatedly taking the smaller of their two front elements. The splitting gives log n levels and each level touches every element once, so the running time is n log n on every input: best case, worst case and average alike.
- Split the range in half. Keep splitting until each piece holds one element, which is sorted by definition.
- Merge two sorted pieces: compare their front elements and copy the smaller one out, advancing that side.
- When one side runs dry, copy the rest of the other side across unchanged.
- Merge upward level by level until one sorted run covers the whole array.
Implementation
def merge_sort(values):
if len(values) <= 1:
return values
middle = len(values) // 2
left = merge_sort(values[:middle])
right = merge_sort(values[middle:])
merged, i, j = [], 0, 0
while i < len(left) and j < len(right):
# <= rather than <, so equal values keep their original order.
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
merged.extend(left[i:])
merged.extend(right[j:])
return mergedWhen to use it
- Use it when stability matters. Equal elements keep their original order, which is what lets you sort by one field and then another.
- Use it for linked lists, where splitting and merging need no extra memory at all and no random access.
- Use it for data that does not fit in memory: the merge step reads sequentially, which is why external sorts are merge sorts.
- Avoid it when memory is tight and stability is not needed; heapsort gets the same guarantee in O(1) space.