Quick Sort

Divide and conquer sorting with visible partition boundaries

Put one pivot in its final place

Quick Sort chooses a pivot, partitions the current range so smaller values are on its left and larger values are on its right, then repeats the same job on both sides. Once partitioning finishes, that pivot is already in its final sorted position.

What the visualization shows

This page uses Lomuto partitioning with the last value as the pivot. The side panel is an explicit interval stack that replaces recursion. Watch the scan pointer move, the less-than region grow, and each pivot become fixed. Change the input to test favorable, reversed, or duplicate-heavy data.

Input

Interval stack: each frame is a pending subarray a[lo..hi]

Stack empty: every position is final

Pop interval [0, 9] from the work stack.

1function quickSort(a: number[]): number[] {
const n = a.length;
const stack: [number, number][] = [[0, n - 1]];
while (stack.length > 0) {
  const [lo, hi] = stack.pop()!;
  if (lo >= hi) continue;
  const pivot = a[hi];
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (a[j] < pivot) {
      [a[i], a[j]] = [a[j], a[i]];
      i++;
    }
  }
  [a[i], a[hi]] = [a[hi], a[i]];
  stack.push([i + 1, hi]);
  stack.push([lo, i - 1]);
}
return a;
20}

n10

Stack depth0

lo0

hi9

pivot-

a[j]-

swapCount0

1 / 93

Complexity and tradeoffs

Average time is O(n log n), auxiliary stack space is typically O(log n), and partitioning is in-place. Quick Sort is not stable. Consistently bad pivots can produce O(n^2) time, so practical implementations randomize or improve pivot selection.

Invariant: before each scan step, values before i are smaller than the pivot, while values from i through the previous scan position are at least the pivot. Keeping that statement true explains why the final pivot swap is correct.

Compare its growth rate in the complexity reference, or continue with Binary Search to see another logarithmic divide-and-conquer pattern.

Algorithm Visualizer

Quick Sort

Put one pivot in its final place

What the visualization shows

Complexity and tradeoffs