Implement Quick Sort in JavaScript

Having worked across sites raking in over 50 billion website visits annually with Higglo Digital I write about tech topics and teach engineers to have solid foundations that will help them get ahead in their career. I also build awesome products for digital nomads — check it out!

Quick sort is a popular and efficient sorting algorithm that works by dividing and conquering an array of data. It operates by selecting a pivot element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively until the base case of an empty or single-item array is reached, at which point the sort is complete.

To implement quick sort in JavaScript, we can define a function that takes in an array and an optional left and right index, which represent the bounds of the portion of the array that should be sorted. If no left and right indices are provided, we can default them to the start and end of the array.

Here is an example of how this function might look:

function quickSort(array, left = 0, right = array.length - 1) {
  // base case: return if the left index is greater than or equal to the right index
  if (left >= right) {
    return;
  }
  // choose pivot element and partition the array
  const pivotIndex = partition(array, left, right);

  // sort the left and right sub-arrays recursively
  quickSort(array, left, pivotIndex - 1);
  quickSort(array, pivotIndex + 1, right);
}

The key to the quick sort algorithm is the partition function, which selects a pivot element and rearranges the elements in the array such that all the elements less than the pivot are on the left side of the pivot and all the elements greater than the pivot are on the right side.

Here is an example of how the partition function might be implemented:

function partition(array, left, right) {
  // choose pivot element (we'll use the rightmost element)
  const pivot = array[right];

  // initialize variables for the left and right indices of the partition
    let i = left;
    let j = right;
    // loop through the array until the left index is greater than or equal to the right index
    while (i < j) {
      // find the first element from the left that is greater than the pivot
      while (array[i] < pivot) {
        i++;
      }
      // find the first element from the right that is less than the pivot
      while (array[j] > pivot) {
        j--;
      }
      // if the left index is less than or equal to the right index, swap the elements and move on to the next pair
      if (i <= j) {
        [array[i], array[j]] = [array[j], array[i]];
        i++;
        j--;
      }
    }
    // return the final index of the pivot element
    return i;
  }

To use the quick sort function, we can simply call it with the array that we want to sort:

const array = [5, 2, 1, 3, 4];
quickSort(array);
console.log(array); // [1, 2, 3, 4, 5]

Quick sort has an average time complexity of O(n log n), making it one of the faster sorting algorithms for large datasets. However, it has a worst-case time complexity of O(n²) when the pivot is chosen poorly, so it is important to choose the pivot carefully to ensure efficient usage.

I founded Higglo Digital and we can help your business crush the web game with an award-winning website and cutting-edge digital strategy. If you want to see a beautifully designed website, check us out.

I also created Wanderlust Extension to discover the most beautiful places across the world with highly curated content. Check it out!