The answer for the first case is given. 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 . 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. 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. Modify the definition of quick-sort to take advantage of this observation.