Pattern #27

Quick Sort

Important interview questions, thinking patterns, in-place partitioning, Quickselect algorithm, Lomuto vs Hoare methods, and Go rules.

Must Solve

12 core questions — solve these first.

1.Sort an Array
Quick Sort in-place partitioning with randomized pivot choicemedium
2.Kth Largest Element in an Array
Quickselect single-branch partition in O(N) average timemedium
3.Kth Smallest Element in an Array
Quickselect target index searchmedium
4.Top K Frequent Elements
Quickselect on bucket frequencies or Min-Heapmedium
5.Sort Colors
Dutch National Flag 3-way partitioning (0, 1, 2) in O(N) single passmedium
6.Wiggle Sort II
Quickselect median finding + 3-way virtual index wiringmedium
7.Find K Closest Elements
Binary search + 2 pointers or Quickselect on distancemedium
8.Boyer-Moore / Majority Element
Quickselect median or voting algorithmeasy
9.Smallest K Elements
Quickselect partition finding first K elementseasy
10.Quickselect
Hoare / Lomuto partition recurse only one target sidemedium
11.Partition an Array
Lomuto / Hoare 2-pointer array partitioning around pivotmedium
12.Sort List / Array Partition Variants
Quick Sort partitioning on linked list or array variantsmedium

Also Important

6 more questions worth practicing.

13.K Closest Points to Origin
Quickselect on Euclidean distance squared (x^2 + y^2)medium
14.Find the Kth Largest Integer in the Array
Quickselect string custom length comparatormedium
15.Minimum Moves to Equal Array Elements II
Quickselect median finding in O(N) timemedium
16.Nuts and Bolts Problem
Dual Quick Sort partitioning with nut and bolt pivotsmedium
17.Dutch National Flag Problem
3-way low/mid/high pointer partitioningmedium
18.Three-Way Partitioning
Partition array into 3 ranges around low and high boundsmedium

How to Think

Need efficient general sorting?Quick Sort (O(N log N) average)
Need only Kth largest/smallest?Quickselect (O(N) average time)
Can I arrange values around one pivot?Smaller | Pivot | Bigger
Need in-place sorting with low extra memory?Quick Sort (O(log N) stack space)

Go Quick Sort & Lomuto Partition Template

In-Place Quick Sort & Partitioning in Go

func quickSort(nums []int, low, high int) {
    if low >= high {
        return
    }

    p := partition(nums, low, high)

    // Recurse on left and right sub-arrays EXCLUDING fixed pivot p!
    quickSort(nums, low, p-1)
    quickSort(nums, p+1, high)
}

func partition(nums []int, low, high int) int {
    pivot := nums[high]
    i := low

    for j := low; j < high; j++ {
        if nums[j] < pivot {
            nums[i], nums[j] = nums[j], nums[i]
            i++
        }
    }

    // Place pivot into its correct final sorted index i
    nums[i], nums[high] = nums[high], nums[i]
    return i
}

👉 Average Time: O(N log N) | Worst Time: O(N²) | Stack Space: O(log N)

Quickselect Algorithm (Kth Element in O(N))

When finding the Kth largest or smallest element, you do not need to sort the entire array! Partition the array and recurse ONLY ONE branch:

func quickselect(nums []int, low, high, k int) int {
    if low == high {
        return nums[low]
    }

    p := partition(nums, low, high)

    if p == k {
        return nums[p] // Target found!
    } else if p > k {
        return quickselect(nums, low, p-1, k) // Target is on the LEFT
    } else {
        return quickselect(nums, p+1, high, k) // Target is on the RIGHT
    }
}

👉 Average Complexity: N + N/2 + N/4 + ... = O(N) time!

Good vs Bad Pivot Choices

Balanced Split (Good Pivot)

Pivot splits array roughly in half (N/2 & N/2). Tree depth = log₂ N. Total time = O(N log N).

Unbalanced Split (Bad Pivot)

Pivot is repeatedly min/max (0 & N-1) on sorted arrays. Tree depth = N. Total time = O(N²). Avoid by selecting random pivots!

Visual Memory Rule

Smaller  |  PIVOT  |  Bigger
Average Time = O(N log N)  |  Worst Time = O(N²) (Bad Pivot)
Quickselect = Recurse ONLY ONE branch for Kth element in O(N) average time!

💡 Golden Rule: "Pick a pivot, put it where it belongs, then solve only the smaller problems around it."

Common Interview Mistakes

1. Re-Including Pivot in Sub-Arrays

Calling quickSort(low, p) instead of quickSort(low, p-1) and quickSort(p+1, high) causes infinite recursion!

2. Wrong Base Case

Using low == high instead of low >= high leads to out-of-bounds access.

3. Assuming Stable Sorting

Standard Quick Sort is UNSTABLE. Swapping elements around pivot changes relative ordering of equal keys.

4. Fully Sorting for Kth Element

Sorting the whole array in O(N log N) when the question asks for Kth largest. Always use Quickselect in O(N) time!

Interview Rules

1. Pivot + partition? → Quick Sort
2. Pivot is fixed permanently in its correct sorted index after partition
3. Average Time Complexity → O(N log N)
4. Worst-case Time Complexity → O(N²) (Avoid by picking randomized pivot)
5. Space Complexity → In-place array modification, O(log N) recursion stack
6. Need Kth largest/smallest? → Quickselect in O(N) average time
7. Sort stability → Quick Sort is Unstable
8. Dutch National Flag (Sort Colors) → 3-way low/mid/high pointer partition in O(N) single pass

Small Rules

Rule 1: After partitioning, pivot reaches its final correct index and is never moved again.
Rule 2: Recurse on left of pivot (low to p-1) and right of pivot (p+1 to high).
Rule 3: Quick Sort works in-place, requiring less memory than Merge Sort.
Rule 4: Quick Sort is unstable because partition swaps equal keys out of order.
Rule 5: Quickselect discards one branch per partition, reducing time from O(N log N) to O(N).

Production Thinking

In-Memory Sorting → Fast in-place array sorting without auxiliary memory allocations

Percentile & Median Finding → Compute 95th/99th percentiles in streaming telemetry using Quickselect

Top K Analytics → Extract top K latency spikes or heavy queries without full O(N log N) sorting

Production Warning → Use standard library pdqsort / introsort which switches to Heap Sort on deep recursion to guarantee O(N log N) worst-case!

Remember This

Quick Sort           → Pivot + Partition
Smaller              → Left
Bigger               → Right
Pivot                → Correct position
Then                 → Sort both sides
Average              → O(n log n)
Worst                → O(n²)
Kth item only        → Quickselect
Good pivot           → Balanced partitions

💡 Golden Rule: "Pick a pivot, put it where it belongs, then solve only the smaller problems around it."