Quick Sort in Javascript

Source: Dev.to

Overview

Quick Sort is a widely used, fast, and elegant divide‑and‑conquer sorting algorithm.
The basic idea:

1. Pick a pivot element.
2. Partition the array so that elements smaller than the pivot go to the left and elements larger go to the right.
3. Recursively apply the same logic to the left and right sub‑arrays.

“Quick Sort is quick because it reduces the problem size drastically at every step.”

Functional (Non‑in‑place) Quick Sort

// functional quick sort
const quickSort = (arr) => {
  if (arr.length  {
  const pivot = arr[high];
  let i = low - 1;

  for (let j = low; j  {
  if (low  {
  const pivot = arr[low];
  let i = low - 1;
  let j = high + 1;

  while (true) {
    do { i++; } while (arr[i]  pivot);

    if (i >= j) return j; // boundary index
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
};

const hoarePartition = (arr, low, high) => {
  const pivot = arr[low];
  let i = low - 1;
  let j = high + 1;

  while (true) {
    do { i++; } while (arr[i] < pivot);
    do { j--; } while (arr[j] > pivot);

    if (i >= j) return j; // boundary index
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
};

const quickSortHoare = (arr, low = 0, high = arr.length - 1) => {
  if (low < high) {
    const p = hoarePartition(arr, low, high);
    quickSortHoare(arr, low, p);
    quickSortHoare(arr, p + 1, high);
  }
  return arr;
};

Example

Before: [34, 56, 3, 234, 6, 7] (pivot = 34)
After partition: [7, 6, 3 | 234, 56, 34] – returns partition index = 2.

Key Differences from Lomuto

• The pivot does not necessarily end at its final sorted position.
• The function returns a boundary index, not the pivot index.
• Fewer swaps → generally faster, especially with many duplicates.

Comparison: Lomuto vs. Hoare

Complexity Analysis

• Space Complexity
  • Functional Quick Sort: O(n) (extra arrays).
  • In‑place Quick Sort: O(log n) (recursion stack).

Summary

• Functional Quick Sort is easy to understand but uses extra memory.
• In‑place Quick Sort with Lomuto or Hoare partitioning is preferred for production code.
• Hoare’s scheme generally offers fewer swaps and better performance with duplicate values, while Lomuto’s scheme is simpler and guarantees the pivot ends in its final position.

Choose the version that best fits the constraints of your environment and the characteristics of the data you need to sort.