Why sort
Line 1 puts eight numbers in a row of memory, one per numbered slot. Sorting puts them in order, smallest first. Sorted data is easier to use: binary search works, and the smallest and largest sit at the two ends.
Insertion sort
Insertion sort grows a sorted part on the left. It lifts the next item, slides each bigger sorted item one slot right, and drops the item into the gap. 3 goes before 6, then 5a (the two 5s are marked a and b) before 6.
The next item, 1, is smaller than everything on its left. Insertion sort compares it with 8, 6, 5a and 3, shifts all four one slot right and drops 1 into slot 0. A small item far to the right costs the most work.
Three more passes finish the row: 20 comparisons in all. A reversed row of 8 needs 28, n(n−1)/2. That is O(n²): double the items, about four times the work. A nearly sorted row needs few shifts, so it is fast.
Merge sort
Merge sort starts again from the same eight numbers. It splits the row in half, then splits each half, until every piece holds one item. One item on its own is already sorted. Eight items take three rounds of halving.
Now merge neighbours. For each pair, compare the two front items, copy the smaller one into the spare row first, then copy the pair back. 6 and 3 become 3, 6; 7 and 2 become 2, 7. That leaves four sorted runs of two.
Next, merge runs of two into runs of four. Look only at the front item of each run, copy the smaller into the spare row, and repeat. Each comparison places one item, so a merge never goes back over items it has placed.
The last merge joins the two runs of four. Each of the 3 rounds placed all 8 items once: 24 placements, n × log₂ n. That is O(n log n). For 1,000 items merge sort needs under 10,000 comparisons; insertion sort can need 499,500.
Stability and Python
The two 5s are equal; the marks a and b show which came first. On a tie the merge takes from the left run, so 5a stays ahead of 5b. A sort that keeps equal items in their original order is stable.
Line 2 hands the job to Python. sorted() uses Timsort: it finds runs in order, sorts short runs with binary insertion sort and merges runs. Under 64 items it is all binary insertion sort. It is stable and O(n log n) at worst.
The Python behind the step
;; step 1/10 · Why sort? >>> nums = [6, 3, 5, 8, 1, 5, 7, 2] >>> nums[0], nums[7] # unsorted: the ends tell you nothing (6, 2) >>> s = sorted(nums) >>> s[0], s[-1] # sorted: smallest and largest (1, 8)
O(n²) and O(n log n) describe how the work grows as the number of items n grows, ignoring constant factors. log₂ n is how many times n can be halved before reaching 1 (log₂ 8 = 3). CPython's sort uses binary insertion sort to build short runs, so for fewer than 64 items it is binary insertion sort alone. Since Python 3.11 it decides the order of merges with Munro and Wild's powersort policy.