Quicksort:
Pick a pivot
Split the array around the pivot
Recursively sort both halves

If you consistently pick bad pivots, it run in THETA (n^2) time, but the expected time for reasonably chosen pivots is THETA (n lg n).

If only you had a way to find the median, the dead center median of an unsorted way, that ran quickly, or at least ran in THETA (n) time, then you could use that median as the quick sort pivot and QuickSort would then run in THETA (n lg n) time (worst case).

Linear Time Selection (Median-of-Medians) algorithm.  Given an unsorted list of elements, and a number i, it will find the ith element in sorted order, in THETA(n) worst-case time, without sorting the array.

This uses recursion in two different ways, which is what it makes it clever.

So, we have a list of elements that are part of a total order.  (For any two elements, a and b, exactly one of the three is true:  a < b, a > b, a=b.  Plus the normal rules of transitivity also apply.)  (The list of elements can be sorted.  Any two can be compared and the list can be sorted.)  We have an integer 1<=i<=n.  The Linear Time Selection will find the ith. element in sorted order in THETA (n) time.

1.  Break the list up into groups of 5.  (5 is a critical number.  3 and it won't run in linear time.  7 is overkill.)  That last group might have fewer than 5 elements if n is not divisible by 5.

2.  Using brute force find the exact median of each of these groups of five.  Set these medians aside.

3.  Using recursion find the EXACT median of this list of medians.  (You are calling the ENTIRE algorithm recursively, not just the break into 5's part.  You are calling the whole algorithm recursivly, including the part of the algorithm I haven't talked about yet.)

4.  Using this median of medians as a pivot, you break up the original list around the pivot (less than the pivot, equal to the pivot, greater than the pivot).  Now this pivot is not guaranteed to be the dead center median of the original list; it is the dead center median of the list of medians.  (However, you can show mathematically that it's not a bad choice for pivot, even if it's not the perfect pivot.)

So, decide which list element i is in.  Since you've partitioned the entire list around the pivot, you know exactly where the pivot goes.  If i is equal to the pivot, you're done.  If i comes before the pivot, use recursion on the BEFORE list.  If i comes after the pivot, use recursion on the AFTER list.

Base cases:  n, the list size is 1 (or 0).  Also, when position i falls into the EQUAL list (when position i is known to be equal to the pivot), you're done then, too.

This algorithm, if you were to use in to find the perfect pivot in QuickSort, would guarantee THETA (n lg n) time for QuickSort...but no one ever uses it.  Because using gives you a "slower" n lg n, than the actual expected runtime that results from using a more crudely, but more quickly chosen pivot.  In other words, if you really want to use linear time selection to make QuickSort "perfect," you might as well use Merge Sort instead (and some people say you should use merge sort anyway).

Shell Sort sorts in place:  (named after the guy who invented it:  Shell)

If I have n items in a list, I come up with some subset of the numbers from 1 to n, the subset MUST include 1, and must NOT include n.

If I want to sort 10 items:  maybe my subset is 5 2 1.

What I then do is I sort all the items that are 5 apart.

Q W E R T Y U I O P
Q U E O P Y W I R T
E I P O Q T R U W Y
E I O P Q R T U W Y

You go your sublist, and sort by "pushing back" elements that are out of order with the one k positions before it, and keep pushing back until you can't any longer.

Obviously, the critical choice here is what the sublist should be.

The "official" Shell Sort:  the sublist contains those numbers with no prime factors other than 2 or 3.  10: 9 8 6 4 3 2 1

If this is your sublist, it is guaranteed that no element gets pushed back more than once on any pass.  So, each pass takes n times.  And there are about lg^2 n elements in each sublist, so it takes n lg^2 n time, not as fast as QuickSort, but way faster than Bubble Sort.