0- Choose the pivot (using the "median-of-three" technique); also, put the smallest of the 3 values in A[low], put the largest of the 3 values in A[high], and swap the pivot with the value in A[high-1]. (Putting the smallest value in A[low] prevents right from falling off the end of the array in the following steps.)
- Initialize: left = low+1; right = high-2
- Use a loop with the condition:
while (left <= right)
The loop invariant is:
all items in A[low] to A[left-1] are <= the pivot
all items in A[right+1] to A[high] are >= the pivot
Each time around the loop:
left is incremented until it "points" to a value > the pivot
right is decremented until it "points" to a value < the pivot
if left and right have not crossed each other,
then swap the items they "point" to.
- Put the pivot into its final place.
