Add

[crisdosaygo]

Bubble sort
Heap sort
Table listing best, average and worst case complexity for everything

[crisdosaygo]

Selection sort , like insertion sort but reversed. insertion sort finds the correct location in the sorted list to insert the next element from the unsorted list or a selection sort finds the largest element from the unsorted list and inserts it into the end of the sorted list

[crisdosaygo]

Categorize into the N squared class and the n log n class, then sort within those classes for practical performance and provide benchmarks from tests (average of 50 runs) on a standard 1000 or 10,000 item list

Also deal with space complexity categorizing into the N, N log n and 1 class and sort within those classes if possible

[crisdosaygo]

Tree sort

[crisdosaygo]

Crit-bit trees - Best of both worlds: hash and heap. Insertion, deletion, and exact search. Plus find minimum and general suffix search.

One example ref: http://cr.yp.to/critbit.html