Practice Now
JavaScript
Quicksort
Recursion
Debugging
Algorithm

Infinite recursion in JavaScript quicksort?

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms
AlgorithmsJavaScript & WebDebugging & Errors

Introduction

Infinite recursion in JavaScript quicksort happens when the partitioning step fails to reduce the problem size — typically because the pivot element is not excluded from the recursive calls, or because all elements end up in one partition. The fix is to ensure the pivot is placed at its final position and excluded from both recursive calls, and that the base case (if (arr.length <= 1) return arr) is correctly handled. The most common bug is including the pivot in the left or right subarray, which means the array size never shrinks and the recursion never terminates.

The Buggy Implementation

javascript
1// BUG: Infinite recursion
2function quicksort(arr) {
3    if (arr.length <= 1) return arr;
4
5    const pivot = arr[0];
6    const left = arr.filter(x => x <= pivot);   // BUG: includes the pivot itself
7    const right = arr.filter(x => x > pivot);
8
9    return [...quicksort(left), ...quicksort(right)];
10}
11
12quicksort([3, 1, 2]);  // RangeError: Maximum call stack size exceeded

The problem: left includes pivot (because 3 <= 3 is true), so left is [3, 1, 2] — the same array. The recursion never reduces the input size.

The Fix: Exclude the Pivot

javascript
1function quicksort(arr) {
2    if (arr.length <= 1) return arr;
3
4    const pivot = arr[0];
5    const left = arr.filter((x, i) => x <= pivot && i !== 0);  // Exclude pivot by index
6    const right = arr.filter(x => x > pivot);
7
8    return [...quicksort(left), pivot, ...quicksort(right)];
9}
10
11console.log(quicksort([3, 1, 4, 1, 5, 9, 2, 6]));
12// [1, 1, 2, 3, 4, 5, 6, 9]

Or more cleanly, use slice to separate the pivot:

javascript
1function quicksort(arr) {
2    if (arr.length <= 1) return arr;
3
4    const pivot = arr[0];
5    const rest = arr.slice(1);  // Everything except the pivot
6    const left = rest.filter(x => x <= pivot);
7    const right = rest.filter(x => x > pivot);
8
9    return [...quicksort(left), pivot, ...quicksort(right)];
10}

Another Bug: Wrong Comparison Operator

javascript
1// BUG: strict less than means equal elements stay in right
2function quicksort(arr) {
3    if (arr.length <= 1) return arr;
4
5    const pivot = arr[0];
6    const rest = arr.slice(1);
7    const left = rest.filter(x => x < pivot);    // Elements equal to pivot go nowhere
8    const right = rest.filter(x => x > pivot);   // Equal elements are lost!
9
10    return [...quicksort(left), pivot, ...quicksort(right)];
11}
12
13quicksort([3, 3, 3]);  // Returns [3] instead of [3, 3, 3]

Fix: use <= for left and > for right (or < and >=):

javascript
const left = rest.filter(x => x <= pivot);
const right = rest.filter(x => x > pivot);

In-Place Quicksort (Lomuto Partition)

The functional-style filter approach creates new arrays. An in-place version is more memory efficient but has its own recursion pitfalls:

javascript
1function quicksort(arr, low = 0, high = arr.length - 1) {
2    if (low < high) {
3        const pivotIndex = partition(arr, low, high);
4        quicksort(arr, low, pivotIndex - 1);   // Exclude pivot
5        quicksort(arr, pivotIndex + 1, high);   // Exclude pivot
6    }
7    return arr;
8}
9
10function partition(arr, low, high) {
11    const pivot = arr[high];
12    let i = low - 1;
13
14    for (let j = low; j < high; j++) {
15        if (arr[j] <= pivot) {
16            i++;
17            [arr[i], arr[j]] = [arr[j], arr[i]];
18        }
19    }
20
21    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
22    return i + 1;
23}
24
25console.log(quicksort([3, 1, 4, 1, 5, 9, 2, 6]));
26// [1, 1, 2, 3, 4, 5, 6, 9]

The key: pivotIndex - 1 and pivotIndex + 1 ensure the pivot is excluded from both recursive calls.

Hoare Partition (Classic)

javascript
1function partition(arr, low, high) {
2    const pivot = arr[Math.floor((low + high) / 2)];
3    let i = low - 1;
4    let j = high + 1;
5
6    while (true) {
7        do { i++; } while (arr[i] < pivot);
8        do { j--; } while (arr[j] > pivot);
9
10        if (i >= j) return j;
11
12        [arr[i], arr[j]] = [arr[j], arr[i]];
13    }
14}
15
16function quicksort(arr, low = 0, high = arr.length - 1) {
17    if (low < high) {
18        const p = partition(arr, low, high);
19        quicksort(arr, low, p);       // Note: p, not p-1 (Hoare's scheme)
20        quicksort(arr, p + 1, high);
21    }
22    return arr;
23}

With Hoare partitioning, the recursive calls use (low, p) and (p + 1, high) — not (low, p - 1) and (p + 1, high) like Lomuto. Using wrong bounds with Hoare causes infinite recursion.

Preventing Stack Overflow with Large Arrays

JavaScript has limited call stack size. For very large arrays, add tail-call optimization manually:

javascript
1function quicksort(arr, low = 0, high = arr.length - 1) {
2    while (low < high) {
3        const p = partition(arr, low, high);
4
5        // Recurse on the smaller partition, iterate on the larger
6        if (p - low < high - p) {
7            quicksort(arr, low, p - 1);
8            low = p + 1;  // Tail call elimination
9        } else {
10            quicksort(arr, p + 1, high);
11            high = p - 1;  // Tail call elimination
12        }
13    }
14    return arr;
15}

This limits the recursion depth to O(log n) regardless of input.

Common Pitfalls

  • Including the pivot in the left or right partition: This is the primary cause of infinite recursion. If the pivot is in left (via x <= pivot without excluding index 0) and no elements go to right, the left array is the same size as the input, causing infinite recursion. Always exclude the pivot from both subarrays.
  • Wrong bounds in Hoare vs Lomuto partition: Hoare partition returns an index where arr[j] may not be the pivot, so the recursive call uses (low, p) and (p+1, high). Using Lomuto-style (low, p-1) with Hoare partition skips elements and causes incorrect sorting or infinite loops.
  • Choosing first/last element as pivot on sorted input: Picking arr[0] or arr[high] as pivot on already-sorted data causes O(n^2) behavior and deep recursion (potentially stack overflow). Use median-of-three or random pivot selection for robustness.
  • Off-by-one in the base case: Using if (arr.length < 1) instead of if (arr.length <= 1) means single-element arrays are still processed, which does not cause infinite recursion but wastes computation. For in-place versions, if (low >= high) is the correct stopping condition.
  • Mutating the array during filter: Using arr.splice() or modifying arr while filtering creates unpredictable behavior. The functional approach should use arr.slice(1) to create a new array excluding the pivot, leaving the original array unchanged.

Summary

  • Infinite recursion occurs when the pivot is not excluded from recursive calls, keeping the subarray the same size
  • Use arr.slice(1) to separate the pivot, then filter the rest into left and right
  • For in-place quicksort, use pivotIndex - 1 and pivotIndex + 1 as bounds (Lomuto) or p and p + 1 (Hoare)
  • Choose median-of-three or random pivots to avoid worst-case O(n^2) on sorted input
  • Optimize tail recursion by iterating on the larger partition to limit stack depth to O(log n)
Related reading
Course
Intermediate
27 lessons
15 hours
DSA Fundamentals

Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.

View the course
Track what you have practised

A free account saves your progress, solutions and study plan across every problem on Codemia.

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms
Codemia
© 2026 Codemia
Resources
Legal
Social
All Rights Reserved.