Sorting Algorithms

Sorting algorithms reorder a collection of elements into a defined sequence. Choosing the right sorting algorithm depends on the size of your data, whether it is partially sorted, and your memory constraints.

Comparison-Based Sorts

These algorithms determine order by comparing pairs of elements. Their theoretical lower bound is O(n log n).

Merge Sort — O(n log n)

Merge sort divides the array in half recursively, sorts each half, then merges them. It is stable and guarantees O(n log n) in all cases, making it the default choice when predictable performance matters.

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    result.push(left[i] <= right[j] ? left[i++] : right[j++]);
  }
  return result.concat(left.slice(i)).concat(right.slice(j));
}

console.log(mergeSort([5, 2, 8, 1, 9])); // [1, 2, 5, 8, 9]

Quick Sort — O(n log n) average

Quick sort picks a pivot, partitions elements around it, then recursively sorts each partition. It is usually faster in practice than merge sort due to better cache locality, but degrades to O(n²) on already-sorted input with a naive pivot.

function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return arr;
  const pivot = partition(arr, lo, hi);
  quickSort(arr, lo, pivot - 1);
  quickSort(arr, pivot + 1, hi);
  return arr;
}

function partition(arr, lo, hi) {
  const pivot = arr[hi];
  let i = lo - 1;
  for (let j = lo; j < hi; j++) {
    if (arr[j] <= pivot) { i++; [arr[i], arr[j]] = [arr[j], arr[i]]; }
  }
  [arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]];
  return i + 1;
}

Simpler O(n²) Sorts

Insertion sort is efficient on small or nearly sorted arrays (used by V8 for short arrays). Bubble and selection sort are mainly educational.

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; }
    arr[j + 1] = key;
  }
  return arr;
}

Non-Comparison Sorts

When input values fall within a known range, you can sort in O(n) using counting sort or radix sort — faster than any comparison-based algorithm.

// Counting sort — works for non-negative integers in range [0, k]
function countingSort(arr, k) {
  const count = new Array(k + 1).fill(0);
  for (const n of arr) count[n]++;
  const result = [];
  for (let i = 0; i <= k; i++) {
    while (count[i]-- > 0) result.push(i);
  }
  return result;
}

Complexity Summary

• Merge sort: O(n log n) time, O(n) space, stable
• Quick sort: O(n log n) avg, O(n²) worst, O(log n) space
• Heap sort: O(n log n) time, O(1) space, not stable
• Insertion sort: O(n²) worst, O(n) best (nearly sorted)
• Counting/Radix: O(n) time when range is bounded

Which to Use

In production code, always prefer your language's built-in sort (JavaScript's Array.prototype.sort, Python's sorted()). Implement sorting manually only in interviews or when you need a specific guarantee like stability, in-place operation, or sub-linear time on bounded data.