Merge sort

How Merge Sort Works

Merge sort is a divide and conquer algorithm. Rather than sorting a whole list at once, it solves the problem by breaking it into smaller and smaller pieces, sorting those pieces, and then combining them back together in the correct order. It works in two distinct phases:

Split phase: Repeatedly divide the list in half until every sublist contains just one item. A single item is always in sorted order by definition.
Merge phase: Repeatedly combine pairs of sorted sublists into a single larger sorted sublist, until the whole list has been reassembled in order.

The key operation is the merge - combining two already-sorted sublists into one sorted sublist by always picking the smaller of the two front elements at each step.

The Merge Operation (Pseudocode)

The logic of merging two sorted sublists into one can be described as:

result ← empty list
WHILE left is not empty AND right is not empty
    IF left[1] <= right[1] THEN
        append left[1] to result
        remove left[1] from left
    ELSE
        append right[1] to result
        remove right[1] from right
    ENDIF
ENDWHILE
append any remaining items in left to result
append any remaining items in right to result

Once one sublist is exhausted, all remaining items in the other sublist are appended directly - they are already in sorted order, so no further comparisons are needed.

Step-by-Step: Full Worked Example

The list [6, 3, 8, 1, 5, 2, 7, 4] is sorted using merge sort below. Each step shows the state of the data at that point in the algorithm. Colour key:

Yellow Front element of a sublist - currently being compared Green Placed into the merged result Grey Waiting in a sublist - not yet compared

The list is halved repeatedly. Colours show the sublist groups at each level.

Level 0 - Original list (1 group of 8):

Level 1 - Split into 2 groups of 4:

Level 2 - Split into 4 groups of 2:

Level 3 - 8 individual items (each is a sorted sublist of length 1):

Every item is now its own sorted sublist. The merge phase can begin.

Each adjacent pair of single items is merged into a sorted pair. The merge of [6] and [3] is shown in detail; the other three pairs follow the same process.

Merging [6] and [3] in detail:

Comparison 1: Compare front of left (6) vs front of right (3)

	Item 1
Left	6
Right	3

3 < 6 → place 3 in result. Right sublist is now empty.

After comparison 1: Left sublist [6] remains. Right is empty - append 6 directly.

Result so far
3	6

Merged result: [3, 6]

Summary - all four pair merges:

Left	Right	Comparison	Merged result
[6]	[3]	3 < 6 → place 3, then append 6	[3, 6]
[8]	[1]	1 < 8 → place 1, then append 8	[1, 8]
[5]	[2]	2 < 5 → place 2, then append 5	[2, 5]
[7]	[4]	4 < 7 → place 4, then append 7	[4, 7]

After Merge Step 1: [3,6] | [1,8] | [2,5] | [4,7] - four sorted pairs.

Merge Step 2: Pairs into groups of 4

Merge [3, 6] and [1, 8]:

Comparison 1: Compare front of left (3) vs front of right (1)

	Front	Waiting
Left [3,6]	3	6
Right [1,8]	1	8

1 < 3 → place 1. Result: [1]

Comparison 2: Compare front of left (3) vs new front of right (8)

	Front	Waiting
Left [3,6]	3	6
Right [8]	8

3 < 8 → place 3. Result: [1, 3]

Comparison 3: Compare front of left (6) vs front of right (8)

	Front
Left [6]	6
Right [8]	8

6 < 8 → place 6. Left is now empty. Append 8 directly. Result: [1, 3, 6, 8]

Similarly, merging [2, 5] and [4, 7]: compare 2 vs 4 → place 2; compare 5 vs 4 → place 4; compare 5 vs 7 → place 5; append 7 → [2, 4, 5, 7]

After Merge Step 2: [1, 3, 6, 8] | [2, 4, 5, 7] - two sorted groups of four.

Merge Step 3 (Final): Full sorted list

Merge [1, 3, 6, 8] and [2, 4, 5, 7] by comparing front elements at each step:

Step	Compare	Pick	Result so far
1	1 vs 2	1	[1]
2	3 vs 2	2	[1, 2]
3	3 vs 4	3	[1, 2, 3]
4	6 vs 4	4	[1, 2, 3, 4]
5	6 vs 5	5	[1, 2, 3, 4, 5]
6	6 vs 7	6	[1, 2, 3, 4, 5, 6]
7	8 vs 7	7	[1, 2, 3, 4, 5, 6, 7]
8	Left = [8], right exhausted	8 (appended)	[1, 2, 3, 4, 5, 6, 7, 8]

The list is now fully sorted. Merge sort always produces a correct result regardless of the original order of items.

Key Takeaways

Merge sort uses a divide and conquer approach: split the list into halves until each sublist has one item, then merge them back in sorted order.
A single item is always in sorted order - this is the base case that makes the algorithm work.
During the merge operation, always compare the front elements of two sublists and place the smaller one into the result.
When one sublist becomes empty during a merge, all remaining items in the other sublist are appended directly - no further comparisons are needed.
Merge sort works on any list - unlike binary search, the original data does not need to be sorted first.
Merge sort is significantly more efficient than bubble sort for large lists, as it halves the problem at each level rather than performing repeated passes.