Quick sort

QuickSort(A,p,r)
if p < r
   // Partition the subarray around the pivot, which ends up in A[q].
   q = Partiton(A,p,r)
   QuickSort(A,p,q-1) //recursively sort the short side
   QuickSort(A,q+1,r) //recursively sort the high side

• The Partition procedure rearranges the subarray A[p:r] in place, returning the index of the dividing point between the 2 sides of the partition.

Partition(A,p,r)
pivot = A[r]                    //the pivot
i = p - 1                   //highest index into the low side
for j = p to r - 1
    if A[j] <= pivot
        i = i + 1
        exchange A[i] with A[j]
exchange A[i+1] with A[r]
return i + 1

• Example on how Partition procedure work: