A discussion of sorts

Programmers seem to go on endlessly about sorting algorithms, without actually saying much.
It took me years to really feel like I completely understood sorting, and even longer before I felt sure what the best sorting algorithm was for any particular situation.
So I've distilled it down to a few salient points, and a few algorithms to consider.

If you don't know what Big-O, or Invariant mean, take a look at things-you-should-know

There are three basic approaches to sorting of note;

Some of the problems that sorting algorithms run into;

And three important algorithms to know about;

Quick Sort - A sort that's actually in use, and quick on average
Merge Sort - A sort that's guaranteed to run quickly, even in the worst-case
Radix Sort, a.k.a. Bucket Sort, a.k.a. Hash Sort. - A sort that looks like it's faster than O(N log N).

There are a number of other sorts that don't really have value, but might be of interest for historical or other reasons..

Bubble Sort - A horrible sort with one interesting property that is for some reason used a lot when teaching programming
Bogo Sort - What happens when someone says "You couldn't write a worse sorting algorithm if you tried"
Heap Sort - An O(N log N) sorting function that's generally confusing and slower than Quick Sort or Merge Sort. Of interest because it defines a heap.