Merge Sort

Quick sort divides using a pivot, and its split can be badly unbalanced. Merge sort always divides exactly in half, giving it a guaranteed O(n log n) bound with no worst-case surprise, at the cost of needing extra memory.

Idea

This is divide and conquer again, but unlike quick sort, the hard work happens after the recursive calls (during the merge), not before (during partitioning).

The merge step

Given two already-sorted arrays, merging them into one sorted array only needs a single left-to-right scan, comparing the fronts of each.

MERGE(LEFT, RIGHT)
// LEFT is the first sorted array
// RIGHT is the second sorted array
 
1. RESULT = empty array
2. i = 0
3. j = 0
4. While i < length(LEFT) AND j < length(RIGHT):
       If LEFT[i] <= RIGHT[j]:
           Append LEFT[i] to RESULT
           i = i + 1
       Else:
           Append RIGHT[j] to RESULT
           j = j + 1
5. Append any remaining elements of LEFT to RESULT
6. Append any remaining elements of RIGHT to RESULT
7. Return RESULT

Worked merge example

Merging [2, 5, 8] and [1, 6, 7]:

LEFT[0]=2 vs RIGHT[0]=1: 1 <= 2, append 1, j advances. Result so far: [1].

LEFT[0]=2 vs RIGHT[1]=6: 2 <= 6, append 2, i advances. Result: [1, 2].

LEFT[1]=5 vs RIGHT[1]=6: 5 <= 6, append 5, i advances. Result: [1, 2, 5].

LEFT[2]=8 vs RIGHT[1]=6: 6 <= 8, append 6, j advances. Result: [1, 2, 5, 6].

LEFT[2]=8 vs RIGHT[2]=7: 7 <= 8, append 7, j advances. RIGHT is now exhausted.

Append the remaining element of LEFT (8):

Merged and sorted, in a single pass over both arrays.

Full algorithm

MERGE_SORT(A)
// A is the array to sort
 
1. If length(A) <= 1:
       Return A
2. MID = length(A) / 2
3. LEFT = MERGE_SORT(A[0 .. MID-1])
4. RIGHT = MERGE_SORT(A[MID .. end])
5. Return MERGE(LEFT, RIGHT)

Recursive splitting, then merging back up

Sorting [38, 27, 43, 3, 9, 82, 10]. The array splits recursively down to single elements:

Then merges back up, each pair combined with a single left-to-right scan:

Why the split is always balanced

Because merge sort always splits exactly at the midpoint, regardless of the values in the array, the recursion tree always has height log₂ n, so no data pattern can make it worse. Quick sort's tree height depends on the pivot choices, which depend on the data, but merge sort's does not.

Complexity

Quick recall

• Split the array in half recursively down to size 0 or 1, then merge sorted halves back together with a single linear scan.
• All the sorting work happens during merge (comparing fronts of two sorted halves), not during the split.
• O(n log n) in every case, best, average, and worst, since the split is always balanced regardless of input.
• Needs O(n) extra space for the merge step; quick sort is in-place but lacks the guaranteed bound.
• Stable: taking the left element on ties preserves original relative order.