They process the list and filter out those items that are smaller and larger, respectively, than the first one. Hence each auxiliary function accepts two arguments, namely, a list of numbers and a number. Each sublist is sorted separately, using quick-sort . Once we get the sorted versions of the two lists, we need a function that combines the two lists and the pivot item. Clearly, all items in list 1 are smaller than the pivot and the pivot is smaller than all items in list 2, so the result is a sorted list.
Figure contains the full function.
The calculation shows the essential steps of the sorting process, that is, the partitioning steps, the recursive sorting steps, and the concatenation of the three parts. From this calculation, we can see that quick-sort implements the process illustrated in figure . Complete the above hand-evaluation. Every time quick-sort consumes a list of one item, it produces the very same list. After all, the sorted version of a list of one item is the list itself.