Quick Sort

Tags

Quick Sort

Category

Sorting

Difficulty

Hard

Problem Statement

Implement the quick sort algorithm to sort an array of integers in ascending order. Quick sort is a divide-and-conquer algorithm that selects a pivot element, partitions the array around the pivot, and recursively sorts the resulting sub-arrays.

Intuition

By choosing a pivot and partitioning the array so that all elements less than the pivot are on its left and all elements greater are on its right, the pivot is placed in its final sorted position. Recursively applying this to the left and right partitions sorts the entire array. The efficiency comes from each partition step doing O(n) work and, on average, halving the problem size.

Approach

  1. Choose a pivot element (commonly the first, last, middle, or random element).
  2. Partition the array around the pivot using two pointers:
    • Move the left pointer right until an element >= pivot is found.
    • Move the right pointer left until an element <= pivot is found.
    • Swap these two elements and continue until pointers cross.
  3. Place the pivot in its correct position.
  4. Recursively sort the left and right sub-arrays.
  5. Base case: sub-array of size 0 or 1 is already sorted.

Pseudocode

function quickSort(array):
    quickSortHelper(array, 0, length(array) - 1)
    return array

function quickSortHelper(array, startIdx, endIdx):
    if startIdx >= endIdx:
        return
    pivotIdx = startIdx
    left = startIdx + 1
    right = endIdx
    while left <= right:
        if array[left] > array[pivotIdx] and array[right] < array[pivotIdx]:
            swap(array[left], array[right])
        if array[left] <= array[pivotIdx]:
            left += 1
        if array[right] >= array[pivotIdx]:
            right -= 1
    swap(array[pivotIdx], array[right])
    // Recurse on the smaller sub-array first for optimal space
    if right - 1 - startIdx < endIdx - (right + 1):
        quickSortHelper(array, startIdx, right - 1)
        quickSortHelper(array, right + 1, endIdx)
    else:
        quickSortHelper(array, right + 1, endIdx)
        quickSortHelper(array, startIdx, right - 1)

Time & Space Complexity

  • Time: O(n log n) average case. O(n^2) worst case when the pivot consistently produces highly unbalanced partitions (e.g., already sorted array with first-element pivot).
  • Space: O(log n) average case for the recursion stack. O(n) worst case. Tail-call optimization (always recursing on the smaller partition first) guarantees O(log n) stack depth.

Key Insights

  • Pivot selection is critical. Random or median-of-three pivot selection avoids worst-case behavior on sorted/nearly-sorted inputs.
  • Quick sort is in-place (no auxiliary arrays), unlike merge sort.
  • It is not stable — equal elements may change relative order.
  • Recursing on the smaller sub-array first ensures O(log n) space even in the worst case for time.
  • Despite O(n^2) worst case, quick sort is often faster in practice than merge sort due to cache locality and smaller constant factors.

Edge Cases

  • Empty array — return immediately.
  • Single-element array — already sorted.
  • Already sorted or reverse-sorted array — worst case for naive pivot selection; mitigated by randomized pivot.
  • All identical elements — proper partitioning logic must handle this to avoid O(n^2).
  • Array with two elements — one comparison and at most one swap.

Linked mentions