Chapter 5: DSA Quicksort
DSA QuickSort – Let’s understand this properly, like I’m sitting next to you explaining it step by step on a whiteboard, with drawings, multiple examples, honest pros & cons, and real code feel.
QuickSort is one of the most important sorting algorithms you will learn in DSA.
It is:
- Very fast in practice
- Widely used in real programming libraries
- Frequently asked in interviews (both to explain and to code)
- Usually the first “efficient” sorting algorithm students learn after the simple O(n²) ones (Bubble, Selection, Insertion)
What is QuickSort? (Core Idea in one sentence)
QuickSort uses divide-and-conquer strategy:
- Pick one element from the array → call it pivot
- Partition the array so that:
- All elements smaller than pivot come to its left
- All elements larger than pivot come to its right
- The pivot is now in its final correct sorted position
- Recursively do the same for left part and right part
That’s it.
QuickSort = choose pivot + partition + recurse left & right
Most Common Pivot Choices (very important)
| Pivot Choice | Comment | Common in Interviews? |
|---|---|---|
| First element | Simple, but bad for already sorted array | Yes |
| Last element | Most common in teaching & code | ★★★★★ |
| Middle element | Slightly better than first | Sometimes |
| Random element | Good average case, used in practice | Advanced |
| Median-of-three | First + middle + last → take median | Very good in practice |
Most common choice in interviews & tutorials = last element as pivot
Step-by-step example (very detailed)
Array: [5, 3, 8, 4, 2, 7, 1, 6]
Let’s use last element as pivot (classic way)
First call Pivot = 6 (last element)
Now partition: Everything < 6 should be on left Everything > 6 should be on right
Process:
i starts from beginning, j is pivot position
We use two-pointer style partition (most common implementation)
After partitioning:
Left side (all ≤ 6): 5 3 4 2 1 Pivot (6) in correct position Right side (all > 6): 8 7
Result after first partition: [5, 3, 4, 2, 1, 6, 8, 7]
Pivot 6 is now in correct sorted position!
Now recurse on left part [5, 3, 4, 2, 1] Pivot = last = 1
Partition around 1:
After partition: [1, 5, 3, 4, 2]
Wait — actually after correct partition: [ nothing < 1 ] 1 [5, 3, 4, 2]
Now left is empty → right [5, 3, 4, 2]
Recurse on [5, 3, 4, 2] Pivot = 2
After partition: [ nothing < 2 ] 2 [5, 3, 4]
Continue like this…
Eventually the whole array becomes sorted:
[1, 2, 3, 4, 5, 6, 7, 8]
QuickSort 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 elements before partition quicksort(arr, low, pi - 1) # Sort elements after partition quicksort(arr, pi + 1, high) def partition(arr, low, high): pivot = arr[high] # choosing last element as pivot i = low - 1 # index of smaller element for j in range(low, high): # If current element is smaller than or equal to pivot if arr[j] <= pivot: i += 1 # increment index of 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 for simplicity) def quick_sort(arr): quicksort(arr, 0, len(arr) - 1) return arr # Example usage numbers = [64, 34, 25, 12, 22, 11, 90, 5] quick_sort(numbers) print(numbers) # Output: [5, 11, 12, 22, 25, 34, 64, 90] |
Time & Space Complexity – Must Know for Interviews
| Case | Time Complexity | When does it happen? |
|---|---|---|
| Best Case | O(n log n) | Pivot always splits array roughly in half |
| Average Case | O(n log n) | Most common case |
| Worst Case | O(n²) | Already sorted / reverse sorted + bad pivot choice |
| Space Complexity | O(log n) average O(n) worst | Recursion stack depth |
Important interview questions about complexity:
- “Why is QuickSort O(n log n) on average but O(n²) in worst case?”
- “How can we avoid the worst case?”
- “Compare QuickSort vs MergeSort in terms of space and real-world performance”
How to Avoid Worst Case in Practice
Common techniques (you should know at least 1–2):
- 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
QuickSort vs Other Sorting Algorithms (Interview Comparison Table)
| Algorithm | Best | Average | Worst | Space | Stable? | In-place? | Real-world usage |
|---|---|---|---|---|---|---|---|
| QuickSort | 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 (stable 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, which is a hybrid of Merge Sort + Insertion Sort — not pure QuickSort.
Summary – QuickSort 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?
Very common follow-up topics I can explain next in the same style:
- How to implement random pivot or median-of-three
- 3-way QuickSort (when many duplicate elements)
- QuickSort vs MergeSort detailed comparison
- Most common QuickSort interview questions (coding + theory)
- How to solve “Kth smallest/largest element” using QuickSelect (same partition idea)
Just tell me which direction you want to go next! 😄
