---
title: Quicksort
description: A divide-and-conquer sorting algorithm with average O(n log n) performance.
tokens: ~344
---

# Quicksort

Quicksort is one of the most widely used sorting algorithms. It works by selecting a pivot element and partitioning the array around it.

## How It Works

1. Pick a **pivot** element from the array.
2. **Partition** — rearrange so elements less than the pivot come before it, and elements greater come after.
3. **Recurse** on the two sub-arrays.

## Example

```typescript
function quicksort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;

  const pivot = arr[Math.floor(arr.length / 2)];
  const left = arr.filter(x => x < pivot);
  const middle = arr.filter(x => x === pivot);
  const right = arr.filter(x => x > pivot);

  return [...quicksort(left), ...middle, ...quicksort(right)];
}

console.log(quicksort([3, 6, 8, 10, 1, 2, 1]));
// [1, 1, 2, 3, 6, 8, 10]
```

## Complexity

| Case | Time | Space |
|---|---|---|
| Best | O(n log n) | O(log n) |
| Average | O(n log n) | O(log n) |
| Worst | O(n²) | O(n) |

### Why O(n²) in the Worst Case?

The worst case happens when the pivot is always the smallest or largest element — the partition is maximally unbalanced. Choosing a random pivot or median-of-three avoids this in practice.

## Compared to Merge Sort

- Quicksort is **in-place** (lower memory overhead).
- Merge sort is **stable** (preserves order of equal elements).
- Quicksort tends to be faster in practice due to better cache locality.