Implementing Quicksort and In-Place Partitioning in JavaScript

Quicksort is one of the most fundamental divide-and-conquer sorting algorithms in computer science. Widely chosen for standard library implementations due to its excellent cache locality and minimal auxiliary memory requirements, Quicksort partitions an array around a chosen pivot element such that smaller values precede the pivot and larger values succeed it.

In JavaScript, understanding how in-place partitioning functions helps developers avoid naive solutions that allocate redundant intermediate arrays at each recursion level.

Example #

Given an unsorted array of numbers, we want to sort the collection in ascending order in-place without allocating extraneous arrays:

const numbers = [38, 27, 43, 3, 9, 82, 10];
quicksort(numbers);
console.log(numbers); // [3, 9, 10, 27, 38, 43, 82]

Implementation #

We implement Lomuto's in-place partitioning scheme with a clean recursive driver:

function swap(arr, i, j) {
  const temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

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

  for (let j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      i++;
      swap(arr, i, j);
    }
  }

  swap(arr, i + 1, high);
  return i + 1;
}

function quicksort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pivotIndex = partition(arr, low, high);
    quicksort(arr, low, pivotIndex - 1);
    quicksort(arr, pivotIndex + 1, high);
  }
  return arr;
}

Complexity Analysis #

• Time Complexity: Average and best-case performance is (O(n \log n)). Worst-case is (O(n^2)) when the array is already sorted and the pivot is systematically chosen as the extreme element.
• Space Complexity: (O(\log n)) auxiliary stack space for recursion when implemented in-place.

Main Point: In-place Quicksort optimizes memory usage and cache locality by swapping elements within the existing array rather than generating intermediate subarrays.

Credits #

Photo by Kalist Strzalkowski on Unsplash

← Home