Computer Science / Unit 3 CS 0145 worked example, 60 to 90 seconds
Merge Sort, Run to the Floor
The idea
Merge sort sorts a list by dividing it into halves until every sublist is one element long — already sorted by definition — then merging adjacent sorted sublists back into larger sorted sublists, at a total cost in O(N log N).
In practice
Take eight shuffled cards. Divide: eight becomes two fours, becomes four twos, becomes eight ones — and eight single cards are eight sorted piles. Now merge, always by comparing the two front cards and taking the smaller. Eight piles merge into four sorted pairs; four pairs merge into two sorted fours; two fours merge into one sorted eight. Three rounds of merging — because eight halves to one in three steps — and each round handles all eight cards once. That is the whole cost story: the number of rounds is the halving count, log of N, and every round touches N cards, which is where N log N comes from. The comparisons did all the work, and no card ever needed a number on its face — heavier-or-lighter was enough.
Where people slip
The merge step is where the sorting actually happens; the dividing only sets the table.
Your place on the trail
Every lesson rests on earlier ones and opens later ones. Tap any to jump.
Builds on
Unlocks
Something wrong in this lesson? Flag it · Sources for Computer Science