Quick Sort

Sorting

avgO(n log n)worstO(n²)spaceO(log n)

Waiting
Current range
Just swapped
In final position

Start with 24 unsorted values

1 / 217

Variables

n=24

Code

function quickSort(a: number[], lo = 0, hi = a.length - 1) {  if (lo >= hi) return a;  const p = partition(a, lo, hi);  quickSort(a, lo, p - 1);  quickSort(a, p + 1, hi);  return a;}function partition(a: number[], lo: number, hi: number) {  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]];  return i;}

procedure quickSort(A, lo, hi)  if lo ≥ hi then return  p ← partition(A, lo, hi)  quickSort(A, lo, p − 1)  quickSort(A, p + 1, hi)end procedure▷ Lomuto partitionprocedure partition(A, lo, hi)  pivot ← A[hi]  i ← lo  for j ← lo to hi − 1 do    if A[j] < pivot then      swap A[i] and A[j]      i ← i + 1    end if  end for  swap A[i] and A[hi]  return iend procedure

def quick_sort(a, lo, hi):    if lo >= hi: return a    p = partition(a, lo, hi)    quick_sort(a, lo, p - 1)    quick_sort(a, p + 1, hi)    return adef partition(a, lo, hi):    pivot = a[hi]    i = lo    for j in range(lo, hi):        if a[j] < pivot:            a[i], a[j] = a[j], a[i]            i += 1    a[i], a[hi] = a[hi], a[i]    return i

Counters

comparisons: 0
swaps: 0

Size24

Distribution

Custom values2 to 150 whole numbers, each 1 to 999

seed 13

Growth by input size

Averaged over seeded runs for each size. Random, Nearly sorted and Reversed use distinct values (the site's own inputs pick values from 5 to 99, so they repeat even in small arrays), so the curves follow the textbook cases. Sizes above 150 are only for this chart; the animation stops at 150.

How it works

Picks the last element as a pivot and partitions the range so smaller elements land to its left (Lomuto scheme); the pivot is then in its final place and both sides are sorted recursively. It is fast in practice, but a bad run of pivots slows it to O(n²).

Complexity

Best: O(n log n)
Average: O(n log n)
Worst: O(n²)
Space: O(log n)
Stable: No
In place: Yes

Quick Sort

How it works

Complexity

Search algorithms