⚡ What Is Quick Sort?
Quick Sort is a divide-and-conquer sorting algorithm.
That means instead of sorting the whole list at once, it divides the list into smaller parts, sorts each part, and then combines them back together.
Think of it like this — if you want to organize a messy pile of books, you might:
- Pick one book as a reference (say, based on its height).
- Move all shorter books to one side and all taller books to the other.
- Then repeat the same process for each smaller pile.
By the end, every book ends up in the right order — without ever comparing every single one directly with every other.
🧩 The Core Idea
Quick Sort works around one key element called the pivot.
Here’s what happens:
- Choose a pivot (any one element from the list — often the first, last, or middle).
- Rearrange the list so that:
- All elements smaller than the pivot come before it.
- All elements greater than the pivot come after it.
This step is called partitioning.
- Recursively apply the same process to the left and right sublists.
- When every sublist has one element left, the whole list is sorted!
🌻 Let’s Understand With an Example
Say we have this unsorted list:
[9, 3, 7, 1, 6, 2]We’ll sort it in ascending order.
Step 1: Pick a pivot
Let’s pick the last element as the pivot: 2.
Now we compare each element with the pivot and rearrange:
- 9 > 2 → goes to the right.
- 3 > 2 → right.
- 7 > 2 → right.
- 1 < 2 → left.
- 6 > 2 → right.
After rearranging:
[1, 2, 9, 3, 7, 6]Now the pivot 2 is in its correct final position.
Everything on the left is smaller, and everything on the right is greater.
Step 2: Repeat on sublists
We now do the same for the two sides.
Left sublist: [1] → already sorted (only one element).
Right sublist: [9, 3, 7, 6]
Pick pivot = 6.
Compare and rearrange:
- 9 > 6 → right
- 3 < 6 → left
- 7 > 6 → right
Result after partitioning:
[3, 6, 9, 7]Now 6 is in its correct spot.
Left = [3], Right = [9, 7]
Step 3: Sort the right part [9, 7]
Pivot = 7.
- 9 > 7 → right
After rearranging: [7, 9]
Everything is now sorted! 🎉
✅ Final Sorted List:
[1, 2, 3, 6, 7, 9]🖼️ Diagram: Quick Sort Visualization
Original: [9, 3, 7, 1, 6, 2]
Pivot = 2
/ \
[1] [9,3,7,6]
Pivot = 6
/ \
[3] [9,7]
Pivot = 7
/ \
[] [9]
Final Sorted: [1, 2, 3, 6, 7, 9]Each time we choose a pivot, the list splits into smaller and smaller groups until every element falls into its perfect place.
🧠 Why Is It Called “Quick”?
Because it’s fast on average.
Unlike Bubble Sort (which compares every element with every other), Quick Sort avoids unnecessary work by cutting the list into smaller chunks each time.
It doesn’t have to sort what’s already sorted — that’s the beauty of divide and conquer.
⚙️ Pseudocode (in simple terms)
QuickSort(arr, low, high):
if low < high:
pivotIndex = partition(arr, low, high)
QuickSort(arr, low, pivotIndex - 1)
QuickSort(arr, pivotIndex + 1, high)
partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j from low to high - 1:
if arr[j] <= pivot:
i = i + 1
swap(arr[i], arr[j])
swap(arr[i + 1], arr[high])
return (i + 1)⏱️ Time and Space Complexity
| Case | Time Complexity | Explanation |
|---|---|---|
| Best Case | O(n log n) | Pivot divides list evenly. |
| Average Case | O(n log n) | Typical performance. |
| Worst Case | O(n²) | Happens if pivot is always smallest or largest (unbalanced splits). |
Space Complexity: O(log n) (due to recursive calls).
🌼 Advantages
✅ Very fast for large lists.
✅ Works well in practice and used widely in real-world systems.
✅ In-place sorting — doesn’t need extra memory.
⚠️ Disadvantages
❌ Performance drops if the pivot selection is poor (e.g., already sorted list).
❌ Recursive calls can use a lot of stack space.
🌟 Real-Life Analogy
Imagine sorting a deck of cards by number.
You pick one card (say, 7) as a reference.
You move all smaller cards to one pile and larger ones to another.
Then you pick new pivots in each pile and repeat.
Eventually, you get a perfectly sorted deck without checking every card against every other card. 🃏
That’s Quick Sort — smart, organized, and efficient.
🧭 In a Nutshell
| Feature | Description |
|---|---|
| Type | Divide and Conquer |
| Key Concept | Pivot-based partitioning |
| Average Speed | O(n log n) |
| Best For | Large datasets |
| Not Ideal For | Already sorted or very small data |
🎨 Simple Summary Diagram
[9, 3, 7, 1, 6, 2]
↓
Pick pivot = 2
→ [1] + [2] + [9,3,7,6]
↓
Pick pivot = 6
→ [3] + [6] + [9,7]
↓
Pick pivot = 7
→ [] + [7] + [9]
Final → [1, 2, 3, 6, 7, 9]About the Author
