Quick Sorting

Easy

Partition around a pivot, recurse on both sides

Problem

Sort the array using quick sort: pick a pivot, partition smaller/larger around it, then recurse on each side.

In simple words

Pick a pivot, shove smaller items left and bigger right, then sort each side.

The idea

Pick a pivot, rearrange so everything smaller sits left of it and everything larger sits right, and the pivot is then in its final position. Recursing on the two sides sorts the whole array in O(n log n) on average, in place — the catch is that a consistently bad pivot degrades it to O(n²).

The trick

The pivot lands in its final spot after one partition; never include it in the recursive calls.
Sorted input with a first-element pivot is the O(n²) worst case — pick a random or median-of-three pivot.
In place (O(log n) stack) but not stable.

←→stepspaceplay

1/21

Optimal

timeO(n log n)spaceO(log n)

In-place, cache-friendly.

1// partition around a pivot, then sort each side2function quick(lo, hi) {3  if (lo >= hi) return;4  const pivot = a[hi];5  let i = lo;6  for (let j = lo; j < hi; j++)7    if (a[j] < pivot) swap(i++, j);8  swap(i, hi);9  quick(lo, i - 1);10  quick(i + 1, hi);11}

Input

array: [7, 2, 1, 6, 8, 5, 3]

Memory

pivot: —
i: —
j: —
piv: —

Output

result: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: nums = [10, 7, 8, 9, 1, 5]
Output:: [1, 5, 7, 8, 9, 10]
Explanation:: Partition around a pivot, then recurse.

Example 2

Input:: nums = [3, 1, 2]
Output:: [1, 2, 3]
Explanation:: Small values go left of the pivot, big ones right.

Example 3

Input:: nums = [2, 2, 1]
Output:: [1, 2, 2]
Explanation:: Duplicates are handled fine.

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.