Chapter 47: DSA Quick Sort
DSA Quick Sort – Let’s understand this algorithm properly, like I’m sitting next to you with a notebook, explaining it slowly, step by step, with lots of small drawings, real examples, and honest comments about when it shines and when it can disappoint.
Quick Sort is one of the most important sorting algorithms you will ever learn.
It is:
- Very fast in practice (often the fastest among comparison-based sorts)
- Widely used in real programming libraries (C++ std::sort, Java Arrays.sort, Python’s sorted() uses a variant)
- Frequently asked in interviews — both to explain and to code
Core Idea in one simple sentence
Quick Sort uses divide and conquer:
- Choose one element called pivot
- Partition the array so that:
- All elements smaller than pivot come to its left
- All elements larger than pivot come to its right
- Pivot itself ends up in its final sorted position
- Recursively do the same thing on the left part and right part
That’s literally it.
The magic is in the partition step — after one partition, the pivot is correctly placed forever.
Most Common Pivot Choices (very important)
Which element you choose as pivot dramatically affects performance.
| Pivot choice | Comment / Behavior | Common in interviews? | Worst-case risk |
|---|---|---|---|
| First element | Simple, but bad if array is already sorted | Yes | High |
| Last element | Most common in teaching & code | ★★★★★ | High if sorted |
| Middle element | Slightly better than first | Sometimes | Medium |
| Random element | Good average case, used in practice | Advanced | Very low |
| Median-of-three | Median of first + middle + last → very good in practice | Very good | Very low |
Most common choice in interviews & tutorials = last element as pivot
Step-by-step example (very detailed)
Array: 38, 27, 43, 3, 9, 82, 10
We’ll use last element as pivot (classic teaching style)
First call Pivot = 10 (last element)
Partition around 10:
We want:
- Left side: all ≤ 10
- Right side: all > 10
After partition (one possible correct arrangement):
3, 9, 10, 27, 38, 43, 82
Pivot 10 is now in correct position!
Now recurse on left part [3, 9] Pivot = 9 (last)
Partition → 3, 9 (3 < 9 → already correct)
Recurse on right part [27, 38, 43, 82] Pivot = 82 (last)
Partition around 82:
Left: all ≤ 82 → everything Right: nothing
Continue recursing on smaller parts…
Eventually the whole array becomes sorted: 3, 9, 10, 27, 38, 43, 82
Quick Sort Code – Most Common Interview Version (Python)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
def quicksort(arr, low, high): if low < high: # pi = partition index – pivot is now at correct position pi = partition(arr, low, high) # Sort left part quicksort(arr, low, pi - 1) # Sort right part quicksort(arr, pi + 1, high) def partition(arr, low, high): pivot = arr[high] # choose last element as pivot i = low - 1 # index of smaller element for j in range(low, high): # If current element ≤ pivot if arr[j] <= pivot: i += 1 # increment position for smaller element arr[i], arr[j] = arr[j], arr[i] # Place pivot in correct position arr[i + 1], arr[high] = arr[high], arr[i + 1] return i + 1 # return pivot position # Wrapper function (most people write this) def quick_sort(arr): quicksort(arr, 0, len(arr) - 1) return arr # Example numbers = [38, 27, 43, 3, 9, 82, 10] quick_sort(numbers) print(numbers) # Output: [3, 9, 10, 27, 38, 43, 82] |
Time & Space Complexity – Must Know for Interviews
| Case | Time Complexity | When does it happen? |
|---|---|---|
| Best Case | O(n log n) | Pivot always splits roughly in half |
| Average Case | O(n log n) | Most common case (random pivot or good data) |
| Worst Case | O(n²) | Already sorted / reverse sorted + bad pivot choice |
| Space Complexity | O(log n) average O(n) worst | Recursion stack depth |
Worst-case scenario (very common interview question):
If array is already sorted and we always pick first or last element as pivot → each partition gives one element on one side and n-1 on the other → O(n²)
How to Avoid Worst Case (very common interview follow-up)
Common practical improvements:
- Random pivot — choose random index each time
- Median-of-three — take median of first, middle, last element
- Switch to Insertion Sort for very small subarrays (n ≤ 10–20)
- Use 3-way partitioning (Dutch National Flag style) when many duplicates exist
Quick Sort vs Other Sorting Algorithms (interview table)
| Algorithm | Best | Average | Worst | Space | Stable? | In-place? | Real-world usage |
|---|---|---|---|---|---|---|---|
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Yes | Very high |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No | High (when stability needed) |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes | Small / nearly sorted |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No | Python, Java, Android |
Quick fact: Python’s sorted() and list.sort() actually use Timsort — a hybrid of Merge Sort + Insertion Sort — not pure Quick Sort.
Summary – Quick Sort in one line each
- Divide-and-conquer sorting algorithm
- Chooses a pivot and partitions the array around it
- Places pivot in its final sorted position after each partition
- Recursively sorts left and right subarrays
- Very fast in practice (average O(n log n))
- In-place sorting (almost no extra space)
- Not stable
- Worst case O(n²) can be avoided with good pivot selection
- One of the most important algorithms for interviews and real coding
Would you like to go deeper into any part of Quick Sort?
Very common follow-up topics I can explain next:
- How to implement random pivot or median-of-three
- 3-way QuickSort (when many duplicate elements)
- Quick Sort vs Merge Sort detailed comparison
- Most common Quick Sort interview questions (coding + theory)
- How to solve “Kth smallest/largest element” using QuickSelect (same partition idea)
Just tell me which one you want — I’ll teach it step-by-step like we’re doing a live session! 😄
