How it works?

Quick Sort follows three steps: pick a pivot, partition, and recurse.

Step-by-Step Process:

1. Pick a pivot: choose one element as the pivot. In this course we always use the last element.
2. Partition: go through the other elements and split them into those less than the pivot and those greater than or equal to it.
3. Recurse: sort the smaller group and the larger group the same way, then put them back together as sorted-smaller + pivot + sorted-larger.

Example on [7, 2, 9, 4]:

• Pivot is 4 (the last element). Partition the rest [7, 2, 9]: less than 4 is [2], the rest is [7, 9].
• Sort [2] (already sorted) and sort [7, 9] (pivot 9, gives [7, 9]).
• Combine: [2] + [4] + [7, 9] = [2, 4, 7, 9].