Latest / Deep End Era. Engineering with Sankalp
Nobody Drops the Whole Box: Comparison Sorts and the n log n Limit
A box of 4,200 trading cards hits the floor of a Leeds card shop, and a father and daughter argue about how to put them back in order. Their ten-minute argument is the history of sorting. Part two of The Deep End's algorithms series explains insertion sort, merge sort, quicksort and heapsort in plain words, proves why no comparison sort can beat n log n, and tells the stories behind them: von Neumann's merge sort for the EDVAC, Tony Hoare's quicksort born in Moscow and a sixpence bet, the adversary that makes library sorts go quadratic, and the comparison bugs that broke production code when…
The skinny
The skinny isn't ready yet — notes appear once the transcript is processed.