The idea behind QuickSort is to replace the MERGE operation in step 3 with the very much faster JOIN operation. If this could be done, while still splitting the list more or less in half in step (1), we would have an algorithm that is clearly faster than Merge Sort. How can we change the way we do step (1) - SPLIT L into pieces - so that we can use JOIN instead of MERGE? This is the secret to QuickSort.
Recall: when is it safe to JOIN two sorted lists L1 and L2?
Answer: When everything in L1 is smaller than everything in L2.
So that's how we cut our list in two. Pick a number, CUTOFF, and put all the elements less than CUTOFF into L1 and all the ones bigger than CUTOFF into L2.
How shall we choose the CUTOFF value? Does it matter?
Answer: We must keep 3 things in mind when we choose
Considering (2) and (3), the very best choice for CUTOFF is the median value in the given list. By definition the median of a list is the value in the list which is larger than exactly half the values in the list.
Let's illustrate quicksort with the list (above) [56,29,35,42,15,41,75,21], assuming that the median is chosen for splitting. At this point I'll also add one little wrinkle - QuickSort actually splits the list into three pieces:
Recursively sort L2.
JOIN L1' LC L2' = [15,21,29, 35 ,41,42,56,75]
Quicksort is very efficient if you use the median as the CUTOFF value, because the list is always split into two equal size pieces. But now we must consider, how efficiently can we compute the median of a list? There is no obvious way to do this quickly - in fact, all the obvious methods require you to sort the list! This obviously is no good - we are trying to use the median to do the sorting, so we can't sort the list in order to compute the median! There are some complex algorithms that do better than this, but in practice people do not use the median, they use something else that is easier to compute:
QuickSort is usually used with arrays. In this case, there is a special version of QuickSort that sorts the array in place i.e. without using any extra memory (normally you would create L1 and L2 by copying the values out of L into them, so you'd need enough space for two whole copies of L). This is done by a complex method of shuffling around the values within the array: the basic idea is not too difficult to understand, but the code itself is very tricky - if you're interested see pages 178-179 in the text.