Sortingintermediatedivide-and-conquerin-placecomparison

Quick Sort

Pick a pivot, partition around it, recursively sort partitions.

How it works

Quick Sort works by selecting a pivot element and rearranging the array so that every element smaller than or equal to the pivot ends up to its left and every larger element ends up to its right. The pivot is then in its final sorted position. The algorithm repeats this partitioning process on the left and right sub-partitions, continuing until all sub-partitions contain a single element.

This implementation uses Lomuto's partitioning scheme with the last element as the pivot and an explicit stack instead of recursion, which avoids stack-overflow risks on large inputs. The partition step scans the subarray with a pointer j; whenever it finds an element ≤ pivot, it swaps it with the element at the boundary pointer i, steadily building the "≤ pivot" region on the left. At the end, the pivot is swapped into position i+1.

The average and best-case time complexity is O(n log n), but the worst case degrades to O(n²) when the input is already sorted (or reverse-sorted) and a naive last-element pivot is used — because each partition contains n−1 elements on one side. Production implementations avoid this with randomised pivot selection or the median-of-three heuristic. Quick Sort is not stable and sorts in-place using only O(log n) stack space on average.

Complexity

Best case

O(n log n)

Average case

O(n log n)

Worst case

O(n²)

Space

O(log n)

In-place

Visualizer

Generating steps…

Where it's used in the real world

C standard library — qsort

General-purpose comparison sort for arrays of any type

Many C runtime implementations (glibc, musl) use an introsort — quicksort with a fallback to heapsort when recursion depth exceeds 2 log₂ n — as the backend for qsort. Quicksort's in-place nature and cache-friendly sequential access make it fast in practice for random data.

C++ std::sort (Introsort)

Default sort algorithm in the C++ Standard Library

GCC's libstdc++ and LLVM's libc++ implement std::sort as introsort: quicksort with a heapsort fallback to guarantee O(n log n) worst case and insertion sort for small partitions. The combination exploits quicksort's average-case speed while eliminating its pathological worst case.

V8 JavaScript engine — Array.prototype.sort

Sorting large JavaScript arrays of numbers

V8 uses Timsort for all arrays, but internally it employs a quicksort-derived partition for the in-place sorting of large numeric arrays where element copying is cheap. Quicksort's minimal allocation overhead and CPU-cache-friendly access patterns matter at the scale of millions of JS operations per second.

Implementation

function quickSort(arr: number[], low = 0, high = arr.length - 1): number[] {
  const a = low === 0 && high === arr.length - 1 ? [...arr] : arr;

  if (low < high) {
    const pivotIdx = partition(a, low, high);
    quickSort(a, low, pivotIdx - 1);
    quickSort(a, pivotIdx + 1, high);
  }

  return a;
}

function partition(arr: number[], low: number, high: number): number {
  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;
}

// Usage
console.log(quickSort([38, 27, 43, 3, 9, 82, 10, 55]));
// [3, 9, 10, 27, 38, 43, 55, 82]

Related algorithms

Merge SortLive

Divide in half, sort each half recursively, merge back.

O(n log n)

Heap SortLive

Build a max-heap, then extract elements one by one.

O(n log n)