Quick Sort

divide-and-conquerin-placeunstable

Press play to start

1function quickSort(arr: number[], lo = 0, hi = arr.length - 1): number[] {
if (lo < hi) {
  const p = partition(arr, lo, hi)
  quickSort(arr, lo, p - 1)
  quickSort(arr, p + 1, hi)
}
return arr
8}
9function partition(arr: number[], lo: number, hi: number): number {
const pivot = arr[hi]
let i = lo - 1
for (let j = lo; j < hi; j++) {
  if (arr[j] <= pivot) {
    [arr[++i], arr[j]] = [arr[j], arr[i + 1]]
  }
}
[arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]]
return i + 1
19}

Step 1/0

Custom array:

Complexity

Best:O(n log n)
Average:O(n log n)
Worst:O(n²)
Space:O(log n)

Description

Selects a pivot element, partitions the array into elements less than and greater than the pivot, then recursively sorts each partition.

When to use

Average O(n log n) with small constant factor. Typically fastest in practice for in-memory sorting. Widely used in system libraries.