## Implementation and Analysis of Quicksort

Quicksort works fundamentally by recursively partitioning an unsorted set of elements until all
partitions contain a single element. In the implementation presented
here, `data`

initially contains the unsorted
set of `size`

elements stored in a single
block of contiguous storage. Quicksort sorts in place, so all
partitioning is performed in `data`

as well.
When *qksort* returns,
`data`

is completely sorted.

As we have seen, an important part of quicksort is how we
partition the data. This task is performed in the function
*partition* (see Example
12.2) . This function partitions the elements between
positions `i`

and
`k`

in `data`

, where
`i`

is less than
`k`

.

We begin by selecting a partition value using the
median-of-three method mentioned earlier. Once the partition value has
been selected, we move from `k`

to the left
in `data`

until we find an element that is
less than or equal to it. This element belongs in the left partition.
Next, we move from `i`

to the right until we
find an element that is greater than or equal to the partition value.
This element belongs in the right partition. Once two elements are
found in the wrong partition, they are swapped. We continue in this
way until `i`

and
`k`

cross. (You may want to consider how we
know that if any one element is in the wrong partition, there is
always one that can be swapped with it.) Once
`i`

and `k`

cross, all elements to the left of the partition value are less than or equal to it, and all elements to the right are ...