Related to the merge sort is a somewhat more efficient procedure called the quick sort. Here we start with a list L: a1, a2, . . . , an, and use a1 as a pivot to develop two sublists L1 and L2 as follows. For i > 1, if al < a1, place ax at the end of the first list being developed (this is L1 at the end of the process); otherwise, place ax at the end of the second list L2.
After all al, i > 1, have been processed, place a1 at the end of the first list. Now apply quick sort recursively to each of the lists L1 and L2 to obtain sublists L11, L12, L21, and L22. Continue the process until each of the resulting sublists contains one element. The sublists are then ordered, and their concatenation gives the ordering sought for the original list L.
Apply quick sort to each list in Exercise 2.