Quick sort (recursion)

Medium TimeO(n log n) average, O(n²) worst SpaceO(n)

Given an array arr of numbers, return them in ascending order, sorted by splitting the rest around a pivot rather than by merging halves. Duplicates are all kept, and an array of 0 or 1 values is already sorted.

Examples

Example 1

Input
arr = [5, 2, 8, 1, 9, 3]
Output
[1,2,3,5,8,9]
The same six values, ascending.

Example 2

Input
arr = [2, 2, 2]
Output
[2,2,2]
Three equal values, and all three come back.

The Code

function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const [pivot, ...rest] = arr;
  const left = rest.filter((x) => x < pivot);
  const right = rest.filter((x) => x >= pivot);
  return [...quickSort(left), pivot, ...quickSort(right)];
}
quickSort([5, 2, 8, 1, 9, 3]);
Done
Step through quickSort([5, 2, 8, 1, 9, 3]) call by call

More like this

All sorting examples (8) →