Math
Sorting race
Three sorts run the same array at the same speed in comparisons, so the first to finish is the one that asked fewer questions. What decides the race is disorder, not size: on a sorted input insertion sort takes 63 comparisons where quicksort takes 2016.
What happens
Three lanes, one array, and one shared budget of work: all three sorts advance by the same number of comparisons - or of moves, if you switch the unit - so the lane that finishes first is the one that needed the least of that unit, not the one drawn faster. Every lane speaks the same language: the two keys being compared are outlined in gold, a key just written flashes green, a pivot carries a red marker, the segment being worked on is bracketed, elements in their final place get a green foot, and the key insertion sort holds floats above the gap it will drop into. Predict the winner before you press Go, or step the race one unit at a time. Try the inputs: on a sorted array insertion finishes almost at once while quicksort with the last element as pivot hits its worst case; reversed is insertion's worst case; with repeated keys the colour is the position in the input, and merge keeps equal keys in order while quicksort mixes them. Each lane also shows the real time of the run on this computer - a third quantity, never the race unit.
Equations used in the module
Equations n elements, and the race is run in COMPARISONS - the quantity the formulas are about insertion sort MOVES an element exactly as many times as the array has inversions: an identity on EVERY permutation, checked over all n! for n <= 8 insertion comparisons = inversions + (n − 1) − (prefix minima at i >= 1); average = n(n−1)/4 + n − H_n EXACTLY: n = 8 -> 19.282142857142858; n = 64 -> 1067.2561090962943 quicksort (Lomuto, last element as pivot) average = 2(n+1)H_n − 4n EXACTLY: n = 8 -> 16.921428571428571; n = 64 -> 360.70581748175005 merge sort worst case = n·ceil(lg n) − 2^ceil(lg n) + 1 - a formula, not a bound: 321 at n = 64, against ceil(lg n!) = 296, the floor of ANY comparison sort the two are equal for n <= 4 and drift apart after it; merge sort also writes n·lg n elements whatever the input - 384 at n = 64 64 elements, every place mixed: 1001 inversions; insertion 1057 comparisons / 1001 moves, merge 307 / 384, quicksort 352 / 306 64 elements, sorted input: insertion 63, merge 192, quicksort 2016 - and 2016 is n(n−1)/2, the WORST case of quicksort merge overtakes insertion at 15 mixed places out of 64 (269 against 246): the threshold is disorder, not size - on a random input merge is ahead from n = 4 equal keys, 64 elements over 8 values: pairs left in reverse order - insertion 0, merge 0, quicksort 77
