Merging Sorted Piles

Lesson 6 of 11 · 7 min · Free, no account needed

What you will learn

To merge two sorted piles, compare only the two top cards; the smaller goes out.
Each comparison places one card, so merging n cards takes at most n - 1 comparisons: O(n).
When one pile runs out, copy the rest of the other. Forgetting that loses cards.

Two friends each keep a sorted list of lap times. Combine them, fast.
Each pile is sorted, fastest on top. Tap the fastest lap of all 10.
Merge the two piles by hand.
Drag the smaller top into Merged. Count the comparisons.
A program merges with two pointers, i and j.
Before each step, tap the list whose card goes into result next.
Merging.
To merge two sorted lists, compare the items under the pointers i and j. The smaller goes into the result and its pointer moves on.
Each comparison places one item, so merging n items takes at most n - 1 comparisons: O(n).
When one list runs out, copy the rest of the other one. It's already in order.
Write the merge.
Loop while both lists have cards left. Then add the leftovers.
This merge loses cards. Run it, then fix it.
Six cards go in. Count what comes out.
Merge rush.
Three pairs of piles, growing. Tap the smaller top, fast, no misses.
Piles of 5 and 7. What's the most comparisons a merge can need?
Every comparison sends one card to the result. The last card is placed without one, because the other pile is already empty.
Two sorted leaderboards of 50 each. Merge them, or sort all 100 from scratch?
Tap the faster plan. Your merge from before runs for real.
Merging is O(n) because it keeps the order both piles already have. Selection sort is O(n²) and ignores it.

Lessons are interactive and need JavaScript. Turn it on to play them.