ReviseAlgo Logo

Sorting Algorithms

Quick Sort & Quick Select

Partition-based sorting and selection — O(N log N) average sort, O(N) average selection.

Last Updated: August 2, 2026 • 25 min read

1. Introduction

What is Quick Sort?

Quick Sort is an highly efficient, in-place sorting algorithm that uses a Divide and Conquer partitioning strategy. It chooses a "pivot" element and rearranges the array so that all elements smaller than the pivot go to its left, and all larger elements go to its right.

Why is it Important?

  • Fast in Practice: Although its worst-case time complexity is O(N²), Quick Sort is typically faster than Merge Sort in practice because of low constant factors and excellent CPU cache locality.
  • Quick Select: The same partitioning algorithm can find the K-th smallest/largest element in an unsorted array in average O(N) time (instead of O(N log N) sorting).

    • Where is it Used?

  • C++ STL: std::sort uses Introsort, which starts with Quick Sort and switches to Heap Sort if the recursion depth exceeds a threshold.
  • Primitive Array Sorting: Java's Arrays.sort() uses a Dual-Pivot Quicksort implementation.

    • 2. Mental Model: Team Captain (Pivot)

    Think of partitioning as picking a team captain (the pivot).

  • The captain stands in the middle of a room.
  • Shorter teammates are sent to the left.
  • Taller teammates are sent to the right.
  • At the end of this process, the captain is in their exact final sorted position, even though the players on their left and right might not be sorted relative to each other yet.

    • We then repeat this process recursively for the left and right groups.

    3. Core Concepts & Implementations

    Lomuto vs. Hoare Partitioning

  • Lomuto Partitioning: Easier to implement. Typically picks the last element as the pivot, uses a single pointer to track smaller elements, and performs swaps.
  • Hoare Partitioning: More efficient in practice. Uses two pointers starting at both ends and moving toward each other, swapping out-of-order pairs. Performs about three times fewer swaps than Lomuto.

    • Quick Select: Finding K-th Element in O(N) Average Time

    Unlike Quick Sort which recurses into both partitioned halves, Quick Select checks if the pivot's final index matches our target index K. If it does, we return it. Otherwise, we recurse only into the half containing K.

    4. Visual Trace: Lomuto Partitioning

    Let's partition [4, 2, 7, 3, 5] around pivot 5 (last element):

    5. Real-World Applications

  • Quick Select for Top-K Problems: Finding the top-10 trending searches from millions of logs using Quick Select avoids sorting the entire dataset, taking average O(N) time instead of O(N log N).
  • Introsort hybrid: Standard library engines use Quick Sort for high-performance sorting, but automatically transition to Heap Sort if recursion depth is too deep (avoiding stack overflows and O(N²) degradation).

    • 6. Interview Perspective

    How Interviewers Ask This Topic

  • "Find the K-th largest element in an unsorted array." -> Quick Select is the standard O(N) average time solution.
  • "Sort an array of colors consisting of 0s, 1s, and 2s." -> Uses a 3-way Quick Sort partition variant (Dijkstra's Dutch National Flag algorithm).

    • Common Mistakes

    Warning: 1. Degenerate O(N²) Performance on Sorted Inputs: Picking the first or last element as the pivot in an already-sorted array results in highly unbalanced splits (1 element vs N - 1 elements). This leads to O(N²) runtime. Always select a random pivot or use median-of-three selection in interviews.
    > 2. Stack Overflow Risks: Standard Quicksort recursively processes both sides. To limit recursive call stack depth to O(log N) in the worst case, always recurse into the smaller partition first, and use tail-call elimination for the larger partition.

    7. Summary

  • Pivot Selection: Essential for maintaining partition balance and avoiding O(N²) worst-case time.
  • In-Place Partitioning: Lomuto uses a single pass; Hoare uses dual-pointers from ends (faster, fewer swaps).
  • Quick Select: Eliminates half the array at each partition, reducing sorting complexity to O(N) average time.

    • 8. Quiz

    Question 1: What is the recurrence relation for the worst-case time complexity of Quick Sort, and what causes it? Answer: T(N) = T(N - 1) + O(N), resolving to O(N²). This occurs when the pivot chosen is always the absolute minimum or maximum element of the partition (e.g., sorting an already-sorted array with first/last element chosen as the pivot).
    Question 2: How does randomized pivot selection guarantee O(N log N) time? Answer: Selecting a pivot uniformly at random prevents adversaries from feeding input arrays that trigger the worst-case partitioning. The mathematical expectation of partition splits is highly balanced (O(N log N) average), with the worst case O(N²) having a probability approaching 0.
    Question 3: Why is Quick Select average-case time complexity O(N), whereas Quick Sort is O(N log N)? Answer: Quick Sort solves both partitions: T(N) = 2T(N/2) + O(N) \implies O(N log N). Quick Select only solves one partition: T(N) = T(N/2) + O(N). Using the geometric series summation: N + N/2 + N/4 + ... ≤ 2N, resulting in O(N) time.
    Question 4: What is the benefit of Hoare's partitioning scheme over Lomuto's? Answer: Hoare's partitioning scheme runs about three times faster on average because it starts from both ends of the partition and only performs swaps when it finds mismatched elements. In contrast, Lomuto's scheme swaps elements even if they are already in the correct relative position.
    Question 5: Is Quick Sort stable? Explain why or why not. Answer: No, Quick Sort is unstable. During partitioning, elements are swapped over long distances across the pivot boundary, which can easily scramble the relative order of duplicate elements.