# Quick Sort

> Sort in-place by picking a pivot, partitioning around it, and recursively sorting each side — O(n log n) average with minimal memory.

- **Category**: Algorithms
- **Subcategory**: sorting
- **Canonical URL**: https://designpattern.fyi/algorithms/quick-sort/

---

## Description
**Intent**: Sort large arrays in-place with average O(n log n) performance and cache-friendly access — no auxiliary array needed.

**Context**: You need a fast general-purpose sort. Merge sort guarantees O(n log n) but allocates O(n) extra memory. Quick sort achieves the same average performance in-place, and its sequential memory access pattern typically makes it faster on real hardware despite identical asymptotic complexity.

**Solution**: Pick a pivot element (last element, random, or median-of-three). Partition the array so everything smaller goes left of the pivot and everything larger goes right. Recursively sort the left and right partitions. No merge step needed — the partitioning itself produces the sorted result in-place.



## Use Cases
General-purpose array sorting where average-case performance and in-place operation matter. When cache performance is important. When stability is not required and you can choose a good pivot strategy.



## Implementation Example

```javascript
function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  const pivot = arr[arr.length - 1];
  const left = [];
  const right = [];

  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return [...quickSort(left), pivot, ...quickSort(right)];
}

// Usage
const unsorted = [64, 34, 25, 12, 22, 11, 90];
console.log(quickSort(unsorted)); // [11, 12, 22, 25, 34, 64, 90]
```



## Trade-offs


### Advantages

- Average O(n log n) — fast in practice on real hardware

- In-place — O(log n) stack space only, no extra array allocated

- Cache-friendly — accesses contiguous memory sequentially

- Often beats merge sort on arrays despite identical asymptotic complexity




### Considerations & Drawbacks

- Worst case O(n²) — triggered by already-sorted input with a naive last-element pivot

- Not stable — equal elements may be reordered relative to each other

- Pivot strategy matters — naive choice invites bad worst-case; random or median-of-three is much safer