Quicksort is a performant sorting algorithm with an average time complexity of O(n log n) though its worst case is O(n^2).

It adopts a divide and conquer approach similar to Mergesort however the choice of a proper pivot greatly impacts performance. For example, a sorter array that has the first value as its pivot yields the worst case result. The best bet when selecting a pivot is to choose the middle.

function quickSort(arr) {
  if (arr.length < 2) {
    return arr;
  }

  const middle = Math.floor(arr.length / 2);
  const pivot = arr[middle];
  const lesser = [];
  const greater = [];

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      lesser.push(arr[i]);
    } else {
      greater.push(arr[i]);
    }
  }

  return quickSort(lesser).concat(pivot, quickSort(greater));
}

const arr = [9, 2, 5, 6, 4, 3, 7, 10, 1, 8];
quickSort(arr.slice()); // [1, 1, 3, 3, 3, 3, 7, 8, 10, 10]



Want to improve your JavaScript? I have a list of recommended JavaScript books.