Quick Sort

Introduction

Quick Sort is a divide-and-conquer sorting algorithm that works by picking a “pivot” element and partitioning the array so that everything smaller goes to the left and everything larger goes to the right. Then it recursively sorts each side. It’s like organizing a messy bookshelf by picking a book in the middle, putting everything shorter to the left and taller to the right, then repeating for each side.

Quick Sort is one of the most widely used sorting algorithms in practice — it’s the default in many standard library implementations because of its excellent average-case performance and low overhead. You’ll want to be familiar with Recursion, Arrays, and Big-O Notation before diving in.

How Quick Sort works

1. Pick a pivot element from the array
2. Partition: rearrange elements so values ≤ pivot are on the left, values > pivot are on the right
3. Recurse on the left and right subarrays
4. Base case: arrays of length 0 or 1 are already sorted

Visual example

[8, 3, 1, 7, 0, 10, 2]   pivot = 7

Partition around 7:
[3, 1, 0, 2]  7  [8, 10]
     ↓                ↓
[1, 0, 2] 3 []    [8] 10 []
    ↓
[0] 1 [2]

Result: [0, 1, 2, 3, 7, 8, 10]

Implementation

Lomuto partition scheme

The simpler partition approach — uses the last element as pivot and maintains a boundary index.

function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pivotIndex = partition(arr, low, high);
    quickSort(arr, low, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, high);
  }
  return arr;
}

function partition(arr, low, high) {
  const pivot = arr[high];
  let i = low - 1;

  for (let j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }

  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

const arr = [8, 3, 1, 7, 0, 10, 2];
console.log(quickSort(arr));  // [0, 1, 2, 3, 7, 8, 10]

def quick_sort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        pivot_index = partition(arr, low, high)
        quick_sort(arr, low, pivot_index - 1)
        quick_sort(arr, pivot_index + 1, high)
    return arr

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1

    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

arr = [8, 3, 1, 7, 0, 10, 2]
print(quick_sort(arr))  # [0, 1, 2, 3, 7, 8, 10]

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;

        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }

    public static void main(String[] args) {
        int[] arr = {8, 3, 1, 7, 0, 10, 2};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(java.util.Arrays.toString(arr));
        // [0, 1, 2, 3, 7, 8, 10]
    }
}

Hoare partition scheme

The original partition algorithm by Tony Hoare. Uses two pointers that move toward each other. It’s more efficient in practice — fewer swaps on average.

function quickSortHoare(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pivotIndex = hoarePartition(arr, low, high);
    quickSortHoare(arr, low, pivotIndex);
    quickSortHoare(arr, pivotIndex + 1, high);
  }
  return arr;
}

function hoarePartition(arr, low, high) {
  const pivot = arr[Math.floor((low + high) / 2)];
  let i = low - 1;
  let j = high + 1;

  while (true) {
    do { i++; } while (arr[i] < pivot);
    do { j--; } while (arr[j] > pivot);

    if (i >= j) return j;
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
}

const arr = [8, 3, 1, 7, 0, 10, 2];
console.log(quickSortHoare(arr));  // [0, 1, 2, 3, 7, 8, 10]

def quick_sort_hoare(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        pivot_index = hoare_partition(arr, low, high)
        quick_sort_hoare(arr, low, pivot_index)
        quick_sort_hoare(arr, pivot_index + 1, high)
    return arr

def hoare_partition(arr, low, high):
    pivot = arr[(low + high) // 2]
    i = low - 1
    j = high + 1

    while True:
        i += 1
        while arr[i] < pivot:
            i += 1
        j -= 1
        while arr[j] > pivot:
            j -= 1

        if i >= j:
            return j
        arr[i], arr[j] = arr[j], arr[i]

arr = [8, 3, 1, 7, 0, 10, 2]
print(quick_sort_hoare(arr))  # [0, 1, 2, 3, 7, 8, 10]

public static void quickSortHoare(int[] arr, int low, int high) {
    if (low < high) {
        int pivotIndex = hoarePartition(arr, low, high);
        quickSortHoare(arr, low, pivotIndex);
        quickSortHoare(arr, pivotIndex + 1, high);
    }
}

static int hoarePartition(int[] arr, int low, int high) {
    int pivot = arr[(low + high) / 2];
    int i = low - 1;
    int j = high + 1;

    while (true) {
        do { i++; } while (arr[i] < pivot);
        do { j--; } while (arr[j] > pivot);

        if (i >= j) return j;
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

The pivot problem

Quick Sort’s performance depends entirely on pivot selection. A bad pivot creates unbalanced partitions.

Worst case: already sorted input

If you always pick the last element as pivot on a sorted array:

[1, 2, 3, 4, 5]  pivot = 5
[1, 2, 3, 4]  5  []        ← one side is empty every time

This gives O(n²) — each partition only removes one element.

Pivot strategies

Last element (Lomuto default) — simple but vulnerable to sorted input.

Middle element (Hoare default) — avoids the sorted-input worst case.

Median-of-three — pick the median of the first, middle, and last elements. Good balance of simplicity and performance:

function medianOfThree(arr, low, high) {
  const mid = Math.floor((low + high) / 2);
  if (arr[low] > arr[mid]) [arr[low], arr[mid]] = [arr[mid], arr[low]];
  if (arr[low] > arr[high]) [arr[low], arr[high]] = [arr[high], arr[low]];
  if (arr[mid] > arr[high]) [arr[mid], arr[high]] = [arr[high], arr[mid]];
  // Place pivot at high - 1
  [arr[mid], arr[high - 1]] = [arr[high - 1], arr[mid]];
  return arr[high - 1];
}

Random pivot — pick a random element. Makes worst case extremely unlikely regardless of input:

function randomizedPartition(arr, low, high) {
  const randomIndex = Math.floor(Math.random() * (high - low + 1)) + low;
  [arr[randomIndex], arr[high]] = [arr[high], arr[randomIndex]];
  return partition(arr, low, high); // standard Lomuto partition
}

Complexity analysis

Space: O(log n) average for the recursion stack, O(n) worst case.

Why O(n log n) average? Each good partition splits the array roughly in half, giving log n levels of recursion. Each level does O(n) work scanning and swapping. So: n × log n.

Why O(n²) worst case? If every partition puts all elements on one side, you get n levels instead of log n. Each level still does O(n) work: n × n.

Quick Sort vs Merge Sort

Quick Sort wins in practice for most cases because it sorts in-place (better cache locality) and has lower constant factors. Merge Sort is preferred when you need stability or guaranteed O(n log n) worst case.

Interview tips

• Know both Lomuto and Hoare partitions — interviewers may ask you to explain the difference
• Be ready to explain the worst case and how to avoid it (randomized pivot)
• Quick Select (finding the k-th smallest element) uses the same partition logic — it’s a common follow-up question
• If asked “which sort would you use?”, Quick Sort is a strong default answer for in-memory sorting of primitives

Practice problems

1. Sort an array (implement Quick Sort from scratch)
2. Kth Largest Element in an Array (Quick Select)
3. Sort Colors (Dutch National Flag — related partition logic)
4. Top K Frequent Elements
5. Wiggle Sort II

Quick Sort’s partition operation is one of the most useful building blocks in algorithm design. Once you understand how partitioning works, problems like Quick Select, Dutch National Flag, and three-way partitioning become much more approachable.