A Short History of Algorithms
This “Short History of Algorithms” poem was written in 2019 as a study aid for Big Tech-style coding interviews. It didn’t make me better, but here it is for anyone else who might enjoy it.
There’s a melody as well, if you’re interested.
Welcome, friend! Let’s begin
A hundred years of algorithm trends.
Hope you learn and don’t get lost
To learn your options and tradeoffs.
Nn-kay, back 1887
Hollerith invented bucket heaven.
Radix sort good for big ranges
(Counting sort for small ones, if that changes).
Downside is space for holding such.
(At least counting bucket don’t hold much.)
Bubble sort simple, but average case dumb.
It’s in place, so at least that’s sumpin’.
Insertion sort has a good side
Simple, stable, in-place, online
And adaptive! Still quadratic
Improved with shell sort, so don’t panic
(In 2006, it’s the foundation
For Library Sort’s gap inclination)
From Von Neumann ’45
Merge sort always n log(n) time
(John brought n log(n) to the table!)
Not in-place, but usually stable
Needs linear space, if you have some
(Natural takes advantage of existing sorted runs)
Alan Turing, ’46
Made push on, pop off just the trick
LIFO for life, pat on the back
For the handy, simple, linear stack
’53 hash table came
To use associative array
Rose to power, king of access
Constant average time means “fastest”
Know how to implement the king!
Need just n space to store the thing.
(But king beware: expect revolution
Without collision resolution!)
In ’55, linked list appears
Newell and co ease insert fears
Constant insert, stash as you go!
But access, pointer overhead woes
Managing data is its thing
Use it to implement other fun things
’59, Donald Shell
Gaps cut back on n^2 hell
Best case linear if you’re lucky
N log-base-2 N if things are fucky
Shell is is to insertion trouble
as Comb sort is to good ol Bubble
It took a village to make Tree Sort
It’s what 1960 BST is for!
Quicksort complexity, but linear space,
So why keep trees around the place?
Search, add, remove, my realtime friend.
Get what you need in just log n
Yes, implementation takes elbow grease
But log n access grows on trees.
Here it is: Quicksort fun!
Thanks, Tony Hoare in ’61
Endpoint pivot, moving pointers
From left and right to midpoint joiner
Does require log(n) stack space
(Not much, but still, not quite in-place)
Time n log(n), but worst: n^2
Call Tim if you find this unfair
Jealous, Williams, ’64
Built heap on old selection school
Complete BST plus edge rule,
Stores in array! To make it fly
Use heapSort and heapify
HeapSort not stable but is in-place
Slower, really, xxthan quicksort, but better worst case
Bayer and pals in ’71
Took tree nodes and painted ’em
Red and black for height balancing rule:
“Root to min/max leaves delta no more than times two.”
Bayer tweaked trees again in ’72
By self-balancing nodes with kids over two
Like k-d soon to be, makes nice neighborhoods
For large data blocks, it’s pretty good.
Behold the stately k-d tree
A ’75 Bentley BST
Doing point cloud users favors
Good for ranges and nearest neighbors
Quicksort-style branching sweeps the nation
Though K dimensions mean no rotation
1980, Cartesian Tree
From Vuillemin, it makes a heap
In such a way that then
In-order gives you back what you put in
’85 Tarjan-Sleator, Splay Tree
Another self-balancing BST
To speed access to what you desire
Zig and zags to keep recent higher
Pugh brewed skip list in ’89
Array search with linked list add? Divine!
Pointer piles need linear space
For sexy log n searching case
Based on probability it’s in subsequence p
Log 1/p n space vs search, so tweak!
In ’92, Cypher and Sanz went to town:
Cubesort keeps insertion time down
Using binary search to find new entries a stay
Self-managing many small dynamic arrays
Tim Peters’s sort in 2002
Won Android, Chrome, and Python, too!
Timsort has worst case n log(n)
Cos small run merge and insert friends
Push run reference on a stack
Gallop mode or binary search ends to put back
Maybe stable, always fun
Needs n space to get it done
That’s all we have! That’s where it ends.
A century of algorithm trends.
Hope you learned and didn’t get lost
To learn your options and tradeoffs.
