Algorithms in JavaScript
You will rarely need to implement a sort by hand — Array.prototype.sort is already heavily tuned. But the thinking behind classic algorithms — how to split a problem, how to recur, how to argue about cost — is the foundation that lets you read other code and pick the right tool when performance matters. This page implements a handful of the most useful algorithms in plain JavaScript.
A word on Big O
Big O describes how the cost of an algorithm grows as the input grows. We drop constants and lower-order terms, and we usually care about the worst case.
O(1) — constant. Hash map lookup, array index.
O(log n) — halving each step. Binary search.
O(n) — one pass. Sum of an array.
O(n log n) — divide and conquer with a linear merge. Mergesort, the JS engine sort.
O(n^2) — nested loops. Bubble sort, naive duplicate check.
O(2^n) / O(n!) — exponential and factorial. Subsets and permutations without pruning.
Binary search
On a sorted array, binary search finds an element in O(log n) by repeatedly cutting the search range in half. The off-by-one bugs hide in the boundary updates, so this is worth memorising.
binary-search.js
function binarySearch(arr, target) {
let lo = 0;
let hi = arr.length - 1;
while (lo <= hi) {
const mid = (lo + hi) >> 1; // floor((lo + hi) / 2)
if (arr[mid] === target) return mid;
if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
binarySearch([1, 3, 5, 7, 9, 11, 13], 9); // 4
binarySearch([1, 3, 5, 7, 9, 11, 13], 4); // -1Merge sort
Merge sort splits the array in half, sorts each half recursively, and merges them in linear time. It is stable and runs in O(n log n) on every input — no worst case to fear.
merge-sort.js
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = arr.length >> 1;
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(a, b) {
const out = [];
let i = 0, j = 0;
while (i < a.length && j < b.length) {
if (a[i] <= b[j]) out.push(a[i++]);
else out.push(b[j++]);
}
while (i < a.length) out.push(a[i++]);
while (j < b.length) out.push(b[j++]);
return out;
}
mergeSort([5, 2, 8, 1, 9, 3]); // [1, 2, 3, 5, 8, 9][ 1, 2, 3, 5, 8, 9 ]
Quick sort — sketch
Quick sort picks a pivot, partitions the array into "less than" and "greater than" piles, and recurses on each. Average O(n log n), worst case O(n^2) when the pivot is consistently the smallest or largest. The basic shape:
quick-sort.js
function quickSort(arr) {
if (arr.length <= 1) return arr;
const [pivot, ...rest] = arr;
const lo = rest.filter(x => x < pivot);
const hi = rest.filter(x => x >= pivot);
return [...quickSort(lo), pivot, ...quickSort(hi)];
}
quickSort([5, 2, 8, 1, 9, 3]); // [1, 2, 3, 5, 8, 9]Breadth-first search
BFS walks a graph layer by layer using a queue. It finds the shortest path on an unweighted graph and is the right default for "minimum steps to reach X" problems.
bfs.js
function bfs(graph, start) {
const queue = [start];
const visited = new Set([start]);
const order = [];
while (queue.length) {
const node = queue.shift();
order.push(node);
for (const next of graph[node] ?? []) {
if (!visited.has(next)) {
visited.add(next);
queue.push(next);
}
}
}
return order;
}
const g = { A: ['B','C'], B: ['D'], C: ['D','E'], D: ['F'], E: ['F'], F: [] };
bfs(g, 'A'); // [ 'A', 'B', 'C', 'D', 'E', 'F' ]Depth-first search
DFS dives down one branch before back-tracking. Recursive DFS is short and elegant; an iterative version uses an explicit stack.
dfs.js
function dfs(graph, node, visited = new Set(), order = []) {
if (visited.has(node)) return order;
visited.add(node);
order.push(node);
for (const next of graph[node] ?? []) {
dfs(graph, next, visited, order);
}
return order;
}
dfs({ A: ['B','C'], B: ['D'], C: ['D','E'], D: ['F'], E: ['F'], F: [] }, 'A');
// [ 'A', 'B', 'D', 'F', 'C', 'E' ]BFS uses a queue and shines on shortest-path / level-order problems.
DFS uses a stack (or recursion) and shines on connectivity, cycle detection, topological sort.
Always track visited when graphs have cycles — without it both will loop forever.
When to use the built-ins
In production code, almost always prefer:
arr.sort((a, b) => a - b)— engines use TimSort or PDQSort, O(n log n) and stable in modern Node and browsers.new Map()/new Set()— hash maps and sets with the right complexity, no manual hashing.Array.from, spread, and array methods over hand-rolled loops — the engines optimise them aggressively.