Algorithm for PartitioningUp:9.6
To sort the records a[i],
+ 1],..., a[j], in place.
quicksort (i, j)
... a[j] contain at least two distinct keys)
let v be the larger of the first two distinct keys;
... a[j] so that for some k between
+ 1 and j,
a[i] ... a[k
- 1] all have keys <v, and
a[k] ... a[j]
all have keys v;
quicksort (i, k - 1);
quicksort (k, j);
v is called the pivot. It could be any element such that
the resulting partition desirably has two equal sized groups.