Prove that the quicksort algorithm on page 371 is correct with the following change: Do not place a1back into the first list. Instead, place a1 between the result of calling quicksort on the elements less than a1 (or less than equal if you want to allow duplicates) and the result of calling quicksort on elements greater than a1.

Page 371 Algorithm:

The quick sort is an efficient algorithm. To sort a1, a2, . . . , an, this algorithm begins by taking the first element a1 and forming two sublists, the first containing those elements that are less than a1, in the order they arise, and the second containing those elements greater than a1, in the order they arise. Then a1 is put at the end of the first sublist. This procedure is repeated recursively for each sublist, until all sublists contain one item. The ordered list of n items is obtained by combining the sublists of one item in the order they occur.