Deeper

Lab · c05.s04.L1

Sorting race

Every comparison returns one yes/no answer, so no comparison sort can use fewer than log2(n!) comparisons, about n log n.

Question: Why can comparison sorting not beat n log n?

Sorting raceLog-log chart of comparisons against array size, 8 to 4096. A gold dashed line marks the floor log2(n!): the fewest yes/no answers that can name one of n! input orders. A navy line for merge sort runs just above it, ratio 1.0 to 1.06; a russet line for insertion sort climbs away to 88.72. A playhead marks one size; three bars and a readout give the floor, both counts, both ratios and the order count. Nothing drops below it.Sorting racecomparison counts against the n log n floormerge sortinsertion sortfloor log2(n!)comparisons, log scale101001k10k100k1M8163264128256512102420484096array size n, log scaleComparisons at this sizebar length on a log scalemeasured: insertion sort and merge sort, fixed shuffled inputfloor16merge17insertion17n = 8possible orders: 10^4.6floor: 16 comparisonsmerge sort: 17 (×1.06 floor)insertion sort: 17 (×1.06 floor)Every comparison is one yes/no answer; the floor counts them.
Re-simulated Re-simulated: comparison counts measured by running insertion sort and merge sort on a fixed shuffled input at the ten sizes, with the floor computed exactly from n!. The frames sweep a playhead from n = 8 to n = 4096; at each size three bars and a readout give the floor, both counts, both ratios and the number of input orders.
Lab controls
64

Arrow keys between the ten sizes; Home and End to the first and last

1200 ms per frame

Arrow keys on the slider

Frame 1 of 10: n = 8Both sorts sit one comparison above the floor at n = 8: 17 against 16, ratios 1.06 and 1.06. With 10^4.6 possible orders there is little to tell apart.

Keyboard: Space plays or pauses, Left and Right step, Home goes to the first frame, End goes to the last frame.

Text description of this lab

Log-log chart of comparisons against array size, 8 to 4096. A gold dashed line marks the floor log2(n!): the fewest yes/no answers that can name one of n! input orders. A navy line for merge sort runs just above it, ratio 1.0 to 1.06; a russet line for insertion sort climbs away to 88.72. A playhead marks one size; three bars and a readout give the floor, both counts, both ratios and the order count. Nothing drops below it.

Return to the section that hosts this lab

Caption status: re-simulated. Every lab declares one of published, re-simulated, schematic, synthetic or interpolated.