Merge Two Sorted Halves

Compare the fronts of the two halves, take the smaller, and move that side on.

The merge step of merge sort combines two sorted halves into one sorted run using two indices, one at the front of each half. This card walks through the merge with those indices, the copy that finishes it once one half runs out, and why it takes time in proportion to the items merged.

The method has three moves:

Point i at the first item of the left half and j at the first item of the right half.
While both halves have items left, compare the item at i with the item at j, put the smaller one in the output, and move that index on by one. On a tie, take the left one.
When one half is empty, copy whatever remains of the other half to the end of the output. Those items are already sorted and are all at least as large as everything placed, so they need no comparing.

The last merge of the eight numbers 5 2 7 4 1 8 3 6 combines 2 4 5 7 with 1 3 6 8. Before the trace, predict the merged output and the number of comparisons it takes.

Show the prediction

The output is 1 2 3 4 5 6 7 8, after 7 comparisons. Each of the first seven items placed costs one comparison; then the left half is empty, and 8 is copied across without one.

The trace shows both halves side by side, the left half in cells 0 to 3 and the right half in cells 4 to 7, with i and j on the fronts. The cells never change: the merge reads them and writes to a separate output, which each frame's note gives.

Merging 2 4 5 7 with 1 3 6 8, one frame per item placed

Inputleft half in cells 0 to 3, right half in cells 4 to 7

Start
1. 2i
2. 4
3. 5
4. 7
5. 1j
6. 3
7. 6
8. 8
The halves 2 4 5 7 and 1 3 6 8 are each sorted. i and j point at their fronts, and the output is empty.
Take 1
1. 2i
2. 4
3. 5
4. 7
5. 1
6. 3j
7. 6
8. 8
1 is smaller than 2, so 1 goes out and j moves on. Output: 1.
Take 2
1. 2
2. 4i
3. 5
4. 7
5. 1
6. 3j
7. 6
8. 8
2 is smaller than 3, so 2 goes out and i moves on. Output: 1 2.
Take 3
1. 2
2. 4i
3. 5
4. 7
5. 1
6. 3
7. 6j
8. 8
3 is smaller than 4, so the right half gives again. Output: 1 2 3.
Take 4
1. 2
2. 4
3. 5i
4. 7
5. 1
6. 3
7. 6j
8. 8
4 is smaller than 6. Output: 1 2 3 4.
Take 5
1. 2
2. 4
3. 5
4. 7i
5. 1
6. 3
7. 6j
8. 8
5 is smaller than 6. Output: 1 2 3 4 5.
Take 6
1. 2
2. 4
3. 5
4. 7i
5. 1
6. 3
7. 6
8. 8j
6 is smaller than 7. Output: 1 2 3 4 5 6.
Take 7
1. 2
2. 4
3. 5
4. 7
5. 1
6. 3
7. 6
8. 8j
7 is smaller than 8. It was the last item of the left half, so i has nothing left to point at. Output: 1 2 3 4 5 6 7.
Copy the rest
1. 2
2. 4
3. 5
4. 7
5. 1
6. 3
7. 6
8. 8
Only the right half has items left, and they are already in order, so 8 is copied across with no comparison. Output: 1 2 3 4 5 6 7 8.

Result1 2 3 4 5 6 7 8

The indices take turns irregularly, j twice, then i, then j, then i twice, because the halves interleave; nothing about the method assumes they alternate. The marker disappears from a half once its index runs past the end, and that is the moment the loop stops and the copy takes over.

Forgetting the copy is the merge's commonest mistake, and it raises no error. The loop stops as soon as either half is empty, so without the copy the items still waiting in the other half are lost. Here only the 8 would go, and the output would hold seven items with no error raised.

Merging two halves with m and n items moves every one of the m + n items exactly once, and makes at most m + n − 1 comparisons, one for each item placed before a half runs out. The fewest is the length of the shorter half, when every item of one half is smaller than every item of the other: merging 1 2 3 4 with 5 6 7 8 compares 4 times and copies the rest. Either way the merge is O(m + n), linear in the items merged, which is the O(n) combine step that gives merge sort its O(n log n).

← → move through sections and cards