SORTING

Shaker Sort
Bubble Sort
Selection Sort
Merge Sort
Quick Sort
Heap Sort
Tree Sort
Shell Sort
Insertion Sort
Selection Bubble Sort
Binary Insertion Sort

Categorize algorithms by their run time.

n^2 sorts:

Bubble Sort, Shaker Sort, Selection Sort, Insertion Sort, Binary Insertion Sort.

If n is the number of elements you're trying to sort, a t(n) is the function of runtime over the number of elements.

t(n) / n is approximately k times n^2.

For practical purposes, if it takes a certain amount of time to sort n elements, it takes four times that time to sort 2n elements.

If it takes a certain amount of time to sort n elements, it takes 100 times as long to sort 10n etlements.

If it takes a certain amount of time to sort n elements,
how long does it take to sort 1000n?  It takes a million times as long!

n^2 sorts:  should never be used.

Merge Sort, Tree Sort, Heap Sort are what are called n lg n  sorts.

The runtime is proportional to n lg n.

log 10 = 1.  log 100 = 2.  log 1000 = 3.

If I multiply the size of the input by 10, I multiply the runtime by 10 lg 10, which isn't much more than 10.

If I mulitiply the size of the input by 1000, I multiply the runtime by 1000 lg 1000, which is 3000, say, which isn't so bad.

Quick Sort, which is n lg n in practice, but luck is involved, and it COULD run in n^2 time, if you're an unlucky sort of person.

Shell Sort is not n lg n, it is n lg^2 n, which is still pretty close.

Tree Sort is as fast as Merge or Quick or thereabouts, but it requires a whole bunch of extra storage space.  And in the days where storage space was harder to come by, that was important.