Quick Sort

sort(S): sort sequence S

1. if (isEmpty(S) || S is singleton) return S;

2. select and delete an element x, called pivot, from S and split the remaining elements into two parts,

Small and Large, such that all the elements in Small

are less than or equal to x and all the elements in

Large are greater than x;

3. sortedSmall = sort(Small);

4. sortedLarge = sort(Large);

5. return sortedSmall+<x>+sortedLarge;