Understanding Quick Sort via JavaScript

Prerequisites

This guide assumes a basic familiarity with JavaScript and recursion. If you need a refresher, review recursion concepts before trying the code examples. The article demonstrates an in-place quicksort implementation so you can compare it with other sorting algorithms in JavaScript.

How quicksort works (quicksort in javascript)

Quicksort is a divide-and-conquer, recursive sorting algorithm that reorders an array by repeatedly partitioning it around a pivot element. The goal of each partition step is to place the pivot in its final position so that all values left of the pivot are less than (or equal to) it, and all values to the right are greater. Then quicksort is applied recursively to the two partitions until the entire array is sorted.

Key ideas

• Pivot element: a value chosen to split the array into two parts.
• Partition: move elements so that smaller items are before the pivot and larger ones after it.
• In-place sorting: quicksort can rearrange elements inside the original array without creating many extra arrays.
• Recursion in JavaScript: quicksort relies on recursive calls; stack depth affects space usage.

Partition (pivot) function explained

A clear and common partition scheme is Lomuto partitioning, which uses the last element as the pivot. The partition function returns the index where the pivot ends up. This implementation uses O(1) extra memory (aside from the recursion stack) and is suitable for illustrating the core ideas of pivot and pointer manipulation.

// Lomuto partition: pivot is the element at index high
function swap(arr, i, j) {
  const tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp;
}

function partition(arr, low, high) {
  const pivot = arr[high];
  let i = low - 1; // pointer for the smaller element

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

  swap(arr, i + 1, high); // place pivot after the smaller elements
  return i + 1; // pivot index
}

In-place quicksort in JavaScript (recursive example)

Below is a compact recursive quicksort that uses the partition function above. It sorts the array in-place and returns the same array reference for convenience.

function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pivotIndex = partition(arr, low, high);
    quickSort(arr, low, pivotIndex - 1);  // sort left side
    quickSort(arr, pivotIndex + 1, high); // sort right side
  }
  return arr;
}

// Example usage:
const unsortedArr = [31,27,28,42,13,8,11,30,17,41,15,43,1,36,9,16,20,35,48,37,7,26,34,21,22,6,29,32,49,10,12,19,24,38,5,14,44,40,3,50,46,25,18,33,47,4,45,39,23,2];
console.log(quickSort(unsortedArr));

Complexity and practical tips

• Time complexity quicksort: average O(n log n), best O(n log n), worst-case O(n^2) when pivots are poorly chosen.
• Space: in-place sorting minimizes extra arrays; recursion stack depth is O(log n) on average and O(n) worst-case.
• Pivot choice matters: picking a random pivot or using median-of-three reduces the chance of worst-case behavior.
• Alternatives: merge sort offers stable O(n log n) performance but uses more memory; compare quicksort vs merge sort in JavaScript depending on stability and memory constraints.
• Partition schemes: Lomuto (shown) is simple to implement; Hoare partition is often faster and uses fewer swaps but has different index handling.

Notes, variations and debugging tips

• To implement an iterative quicksort in JavaScript, replace recursion with an explicit stack of index ranges.
• If you need a stable sort or guaranteed O(n log n) time, prefer merge sort or TimSort (used by many standard libraries).
• For performance testing, use the JavaScript performance API to benchmark quicksort against other sorting algorithms JavaScript implementations.
• When visualizing quicksort, highlight the pivot, pointer movement, and swaps to make the partition step easier to understand.

Conclusion

Quicksort in JavaScript is a powerful, memory-efficient sorting algorithm when implemented in-place. Understanding pivot selection, partition schemes, and recursion depth will help you write robust quicksort code and choose the right sorting algorithm for your use case.