QuickSort

Category: Classical
Difficulty: Intermediate
Time Complexity: O(n log n)
Space Complexity: O(log n)

Overview

QuickSort selects a pivot element, partitions the array so all elements less than the pivot come before it and all greater come after, then recursively sorts the sub-arrays. Average-case O(n log n) but worst-case O(n²) when the pivot is poorly chosen.

Try It

Web: Open in Eigenvue →

Python:

import eigenvue
eigenvue.show("quicksort")

Default Inputs

{
  "array": [
    38,
    27,
    43,
    3,
    9,
    82,
    10
  ]
}

Input Examples

Default unsorted

{
  "array": [
    38,
    27,
    43,
    3,
    9,
    82,
    10
  ]
}

Already sorted (worst case)

{
  "array": [
    1,
    2,
    3,
    4,
    5,
    6,
    7,
    8
  ]
}

With duplicates

{
  "array": [
    5,
    3,
    8,
    3,
    2,
    5,
    1
  ]
}

Reverse sorted

{
  "array": [
    8,
    7,
    6,
    5,
    4,
    3,
    2,
    1
  ]
}

Code

Pseudocode

function quickSort(array, low, high):
  if low < high:
    pivotIdx = partition(array, low, high)
    quickSort(array, low, pivotIdx - 1)
    quickSort(array, pivotIdx + 1, high)

function partition(array, low, high):
  pivot = array[high]
  i = low - 1
  for j = low to high - 1:
    if array[j] <= pivot:
      i++
      swap(array[i], array[j])
  swap(array[i + 1], array[high])
  return i + 1

Python

def quicksort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        pi = partition(arr, low, high)
        quicksort(arr, low, pi - 1)
        quicksort(arr, pi + 1, high)

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

JavaScript

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

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;
}

Key Concepts

Divide and Conquer

QuickSort divides the problem by partitioning around a pivot, conquers by recursively sorting sub-arrays, and combines trivially (the array is sorted in-place).

Lomuto Partition

The Lomuto scheme picks the last element as pivot and maintains a boundary i: everything at or before i is ≤ pivot. Simple to implement but O(n²) on already-sorted input.

In-Place Sorting

QuickSort sorts in-place using O(log n) stack space for recursion. No auxiliary array is needed (unlike Merge Sort).

Not Stable

QuickSort is not stable — the partition step can change the relative order of equal elements.

Common Pitfalls

Worst-case O(n²): With Lomuto partition and already-sorted input, each partition removes only one element, leading to O(n²). Randomized pivot or median-of-three avoids this in practice.
Off-by-one in partition: The boundary i starts at low - 1 (NOT low). The pivot swap goes to i + 1 (NOT i). Getting these wrong corrupts the invariant.

Quiz

Q1: What is the worst-case input for QuickSort with last-element pivot?

A) Random array
B) Already sorted array
C) Array with all equal elements
D) Both B and C

Show answer

Answer: D) Both B and C

Both already-sorted and all-equal arrays cause the worst case with Lomuto partition. Each partition puts all elements on one side, giving n partitions of n-1 elements each → O(n²).

Q2: Is QuickSort stable?

A) Yes
B) No