DEV Community

Cover image for Quick Sort in Javascript
Alok Kumar
Alok Kumar

Posted on

Quick Sort in Javascript

#computerscience #algorithms #tutorial #javascript

Quick Sort is one of the most important and widely used sorting algorithms.

It’s fast, elegant, and a favorite in interviews — if you understand it properly.

This post explains Quick Sort from basics to advanced, covering:

  • Simple (functional) Quick Sort
  • In-place Quick Sort
  • Lomuto partition scheme
  • Hoare partition scheme
  • Pros & Cons
  • Time and space complexity

What is Quick Sort?

Quick Sort is a divide-and-conquer algorithm.

The idea is simple:

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

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

Simple (Functional) Quick Sort

Let’s start with the most intuitive version.

const quickSort = (arr) => {
  if (arr.length <= 1) {
    return arr;
  }

  let pivot = arr[0];
  let left = [];
  let right = [];

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

  return [...quickSort(left), pivot, ...quickSort(right)];
};
Enter fullscreen mode Exit fullscreen mode

How this works

  • Base case: arrays of size 0 or 1 are already sorted
  • Pivot chosen as the first element
  • Remaining elements are split into left and right
  • Recursively sort both halves
  • Combine results

Pros

  • Very easy to read and explain
  • Great for learning and interviews

Cons

  • ❌ Not in-place
  • ❌ Uses extra memory
  • ❌ Worst-case O(n²) when pivot choice is bad

In-place Quick Sort

In-place Quick Sort:

  • Does not create extra arrays
  • Uses indexes and swaps
  • Much more space-efficient
  • Preferred in real systems and interviews

The key to in-place Quick Sort is the partitioning step.

Lomuto Partition Scheme

Idea

  • Pivot = last element
  • i keeps track of the “smaller than pivot” region
  • j scans the array

Code

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

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

  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
};
Enter fullscreen mode Exit fullscreen mode

What happens here

Before:
[34, 56, 3, 234, 6, 7]   pivot = 7

After partition:
[3, 6 | 7 | 56, 234, 34]
Enter fullscreen mode Exit fullscreen mode

The pivot (7) is now in its final sorted position.

Quick Sort using Lomuto 

const quickSort = (arr, low = 0, high = arr.length - 1) => {
  if (low < high) {
    const pivot = lomutoPartition(arr, low, high);
    quickSort(arr, low, pivot - 1);
    quickSort(arr, pivot + 1, high);
  }
  return arr;
};

let arr = [34, 56, 3, 234, 6, 7];
quickSort(arr);
Enter fullscreen mode Exit fullscreen mode

Lomuto — Pros & Cons

Pros

  • Simple and easy to implement
  • Pivot ends in correct sorted position
  • Excellent for interviews

Cons

  • More swaps
  • Performs poorly with many duplicates
  • Slightly slower than Hoare

Hoare Partition Scheme

Idea

  • Pivot = first element
  • Two pointers:
    • i moves from left
    • j moves from right
  • Swap elements on the wrong side

Code

const hoarePartition = (arr, low, high) => {
  let 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;

    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
};
Enter fullscreen mode Exit fullscreen mode

What happens here

Before:
[34, 56, 3, 234, 6, 7]   pivot = 34

After partition:
[ 7, 6, 3 | 234, 56, 34 ]
Enter fullscreen mode Exit fullscreen mode

Then it returns the partition index = 2.

Quick Sort using Hoare 

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;
};
Enter fullscreen mode Exit fullscreen mode

Lomuto vs Hoare

Lomuto:

  • Pivot goes to its final sorted position
  • Everything left < pivot, everything right > pivot
  • Returns pivot index

Hoare:

  • Pivot does NOT move to final position
  • It only splits the array into two valid halves
  • Returns a partition index, not pivot index
  • Fewer swaps → faster

Hoare says:
“I don’t care where pivot ends up — I only ensure left side ≤ pivot and right side ≥ pivot.”

Why recursive calls look different from Lomuto ?


// lomuto 
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
// hoare

quickSort(arr, low, partitionIndex);
quickSort(arr, partitionIndex + 1, high);
Enter fullscreen mode Exit fullscreen mode

Because:

  • Lomuto returns pivot index
  • Hoare returns boundary index

Summary:

Feature Lomuto Hoare
Simplicity ⭐⭐⭐⭐ ⭐⭐
Swaps More Fewer
Speed Slower Faster
Pivot placement Exact index Not guaranteed
Duplicate handling Poor Better

Time and Space Complexity

Time Complexity

Case Complexity
Best O(n log n)
Average O(n log n)
Worst O(n²)

Worst case occurs when pivot selection is poor (already sorted array).

Space Complexity

  • Functional Quick Sort → O(n)
  • In-place Quick Sort → O(log n) (recursion stack)

Top comments (0)