# 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.