What is Quick Sort?

Quick Sort is a Divide and Conquer algorithm.

Idea:

1. Pick a pivot element
2. Partition the array so that
   • elements smaller than pivot go left
   • elements greater than pivot go right
3. Recursively apply Quick Sort on left & right parts

Mental model:

“Put the pivot in its correct position, everything else fixes itself.”

Step-by-Step Example

Given array

[10, 7, 8, 9, 1, 5]

We’ll use last element as pivot (most common in interviews).

Step 1: Pivot = 5

Partition:

• Elements ≤ 5 → left
• Elements > 5 → right

After partition: