Quick Sort is typically the fastest sorting algorithm in practice. It uses partitioning to place one number (the 'Pivot') in its exact final spot.
We pick the last element (4) as our 'Pivot'. Our goal: Put all smaller numbers to its left, and larger numbers to its right.
6 > 4. It belongs on the right. We do nothing but continue scanning.
2 <= 4. It belongs on the left! We swap it with the first 'large' number we found.
We move the boundary (orange wall) and swap 2 to the safe zone.
5 > 4. Too big. Ignore.
9 > 4. Too big. Ignore.
1 <= 4. Found another small one! We must rescue it from the sea of large numbers.
We advance the boundary and swap 1 with the next available large number (6).
7 > 4. Ignore.
We are done scanning. The boundary is at index 1. The Pivot (4) goes immediately after it, at index 2. We swap 4 with 5.
Pivot 4 is locked. Now we recurse on the left sub-array: [2, 1]. Pivot is 1.
2 > 1. We just swap Pivot (1) with the first large element (2).
Remaining element 2 is a list of size 1. It is automatically sorted.
Now for the right side: [9, 6, 7, 5]. We pick 5 as Pivot.
9 > 5. 6 > 5. 7 > 5. All are larger! The 'orange wall' never moves.
Swap Pivot (5) with the first element (9). 5 finds its home.
Last chunk: [6, 7, 9]. Pivot 9.
6 < 9. 7 < 9. They stay put. 9 stays put.
Every element has found its place. The array is fully sorted.
On average, O(n log n). But if the pivot choice is bad (e.g. smallest element), it degrades to O(n²)! Randomized pivots usually fix this.