Implement QuickSort from Scratch in JavaScript

QuickSort is a fundamental algorithm widely used in the real world due to its efficiency and elegant use of recursion and partitioning. Understanding how QuickSort works under the hood gives you a deeper appreciation of algorithmic thinking and big-O performance. In this blog post, we’ll implement QuickSort from scratch in JavaScript, step-by-step, explore how it works, and test it for performance using a variety of sample arrays.

1. What is QuickSort and Why Use It?

QuickSort is a divide-and-conquer sorting algorithm. It works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays: those less than the pivot and those greater. The same strategy is then recursively applied to the sub-arrays.

Time complexity (average case): O(n log n)
Time complexity (worst case): O(n²)
Space Complexity: O(log n), due to recursion stack

QuickSort is often faster in practice than other O(n log n) algorithms like MergeSort, particularly for in-memory sorting, because it utilizes the cache more efficiently and sorts in place.

2. Writing the Basic QuickSort Function

Let’s start implementing QuickSort in JavaScript with a readable and efficient recursive version. First, we’ll lay down the basic function skeleton.

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)];
}

Explanation: We pick the last element as the pivot. Then we partition the remaining elements into left and right arrays based on whether they're less than or greater than the pivot. Finally, we recursively call quickSort on the partitions.

This version is easy to understand but not optimal in terms of memory—it creates new arrays at every step.

3. Optimizing with In-Place Partitioning

To achieve better space efficiency, we can implement QuickSort in-place. We’ll write a partition function that rearranges elements and returns the pivot index.

function quickSortInPlace(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    const pivotIndex = partition(arr, left, right);
    quickSortInPlace(arr, left, pivotIndex - 1);
    quickSortInPlace(arr, pivotIndex + 1, right);
  }
  return arr;
}

function partition(arr, left, right) {
  const pivot = arr[right];
  let i = left - 1;

  for (let j = left; j < right; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
  return i + 1;
}

How it works: This version swaps elements inside the array itself to avoid creating subarrays. The partition function keeps track of small and large values and arranges them relative to the pivot.

Tip: Choose the pivot wisely (not always the last element). Random or median-of-three pivots help avoid worst-case performance on sorted or nearly sorted arrays.

4. Testing with Arrays of Various Sizes

Let’s test our QuickSort and benchmark it against the native array sort function.

function generateRandomArray(size) {
  return Array.from({ length: size }, () => Math.floor(Math.random() * 10000));
}

const testArray = generateRandomArray(10000);

console.time('Native Sort');
[...testArray].sort((a, b) => a - b);
console.timeEnd('Native Sort');

console.time('QuickSort In-Place');
quickSortInPlace([...testArray]);
console.timeEnd('QuickSort In-Place');

console.time('Non-InPlace QuickSort');
quickSort([...testArray]);
console.timeEnd('Non-InPlace QuickSort');

This test runs three sorts on a 10,000-element array. Note how the in-place algorithm performs closer to the native sort due to lower memory usage. While fully optimized engines will make native sort faster, our QuickSort approaches it in performance for educational and specific control-required use cases.

5. Real-World Use Cases and Considerations

Where QuickSort shines:

Sorting large in-memory arrays quickly
Writing custom sort logic for objects by adapting the comparison logic
Learning recursion and divide-and-conquer patterns

Caution: JavaScript engines may optimize for tail calls differently—recursive stack depth can be a limitation in environments without proper tail call optimization (e.g., browsers).

Parallel Optimization Tip: QuickSort is naturally parallelizable. Libraries or environments that support Web Workers or node clustering can run partitioning jobs in parallel for even faster performance on massive datasets.

To make it more robust in real-world apps, consider augmenting the pivot selection strategy and handling sorted or small partitions with insertion sort for hybrid performance.

Conclusion

Implementing QuickSort from scratch deepens your understanding of algorithm design, recursion, and performance tuning. While not always needed in day-to-day JavaScript thanks to built-in sort functions, knowing how QuickSort works allows you to tune sorting for specific use cases or build sorting algorithms from first principles in interviews, games, or even back-end processing pipelines.

Now that you’ve seen how QuickSort works, try extending it—maybe implement dual-pivot QuickSort or compare with MergeSort or HeapSort for different profiles. Happy sorting!

Useful links: