Divide and conquer

Quick sort is another divide and conquer algorithm, like merge sort. It picks an element and partitions the array around it, then recursively sorts the two partitions. This will become clearer with an example.

---

Pivot

To partition, we pick one element as the pivot. There are several ways to do this:

• Take the first element
• Take the last element
• Pick a random element as pivot
• Pick the median as the pivot

After picking the pivot, we need to partition the array into two halves with a pivot in the middle such that the left part only has elements less than the pivot and the right part has elements only greater than the pivot. Then recursively do this for the left and right partition.

The illustrations below pick the first element as the pivot.