Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The largest element "bubbles" to the end each pass.
function bubbleSort(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}
Time: O(n²) | Space: O(1) | Stable: Yes
Selection Sort divides the array into sorted and unsorted parts. It repeatedly finds the minimum element from the unsorted part and places it at the beginning.
function selectionSort(arr) {
for (let i = 0; i < arr.length; i++) {
let minIdx = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIdx]) minIdx = j;
}
[arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
}
return arr;
}
Time: O(n²) | Space: O(1) | Stable: No
Insertion Sort builds the sorted array one element at a time by picking the next element and inserting it into its correct position among the already sorted elements.
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let key = arr[i], j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
return arr;
}
Time: O(n²) worst, O(n) best | Space: O(1) | Stable: Yes
Merge Sort uses divide and conquer: split the array in half recursively, sort each half, then merge the sorted halves back together.
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(l, r) {
const res = [];
let i = 0, j = 0;
while (i < l.length && j < r.length)
res.push(l[i] < r[j] ? l[i++] : r[j++]);
return [...res, ...l.slice(i), ...r.slice(j)];
}
Time: O(n log n) | Space: O(n) | Stable: Yes
Quick Sort picks a pivot, partitions the array so elements smaller go left and larger go right, then recursively sorts both partitions.
function quickSort(arr, lo = 0, hi = arr.length - 1) {
if (lo < hi) {
const pivot = arr[hi];
let i = lo;
for (let j = lo; j < hi; j++) {
if (arr[j] < pivot) {
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
}
}
[arr[i], arr[hi]] = [arr[hi], arr[i]];
quickSort(arr, lo, i - 1);
quickSort(arr, i + 1, hi);
}
return arr;
}
Time: O(n log n) avg, O(n²) worst | Space: O(log n) | Stable: No
Heap Sort builds a max-heap from the array, then repeatedly extracts the maximum element and places it at the end.
function heapSort(arr) {
const n = arr.length;
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) heapify(arr, n, i);
for (let i = n - 1; i > 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]];
heapify(arr, i, 0);
}
return arr;
}
function heapify(arr, n, i) {
let largest = i, l = 2*i+1, r = 2*i+2;
if (l < n && arr[l] > arr[largest]) largest = l;
if (r < n && arr[r] > arr[largest]) largest = r;
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
heapify(arr, n, largest);
}
}
Time: O(n log n) | Space: O(1) | Stable: No
Counting Sort is a non-comparison sort that counts occurrences of each value and uses the counts to place elements in sorted order. Works for integers in a known range.
function countingSort(arr) {
const max = Math.max(...arr);
const count = new Array(max + 1).fill(0);
arr.forEach(v => count[v]++);
const result = [];
count.forEach((c, i) => {
for (let j = 0; j < c; j++) result.push(i);
});
return result;
}
Time: O(n + k) where k = range | Space: O(k) | Stable: Yes
Radix Sort sorts numbers digit by digit, from the least significant to the most significant, using a stable sort (like counting sort) at each digit level.
function radixSort(arr) {
const max = Math.max(...arr);
for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
const buckets = Array.from({length: 10}, () => []);
arr.forEach(n => buckets[Math.floor(n / exp) % 10].push(n));
arr = buckets.flat();
}
return arr;
}
// radixSort([170, 45, 75, 90, 802, 24, 2, 66])
// => [2, 24, 45, 66, 75, 90, 170, 802]
Time: O(d · (n + k)) where d = digits | Space: O(n + k)
Comparison of common sorting algorithms:
| Algorithm | Best | Average | Worst | Space |
|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) |
For most cases, Quick Sort is fastest in practice. Use Merge Sort when stability is needed.
A stable sorting algorithm preserves the relative order of elements with equal keys. If two elements have the same value, they appear in the same order in the output as in the input.
// Example: sorting by age (stable preserves name order)
// Input: [{name:"B", age:25}, {name:"A", age:25}]
// Stable: [{name:"B", age:25}, {name:"A", age:25}]
// Unstable may swap B and A
Stable: Bubble, Insertion, Merge, Counting, Radix
Unstable: Selection, Quick, Heap
Counting Sort is non-comparison based. It counts occurrences of each value, builds a prefix-sum array, then places elements at correct positions. Best for small integer ranges.
function countingSort(arr) {
const max = Math.max(...arr);
const count = new Array(max + 1).fill(0);
for (const n of arr) count[n]++;
// Build prefix sums (cumulative)
for (let i = 1; i < count.length; i++) count[i] += count[i-1];
const output = new Array(arr.length);
for (let i = arr.length - 1; i >= 0; i--) {
output[--count[arr[i]]] = arr[i];
}
return output;
}
// Input: [4,2,2,8,3,3,1] => Output: [1,2,2,3,3,4,8]
// Input: [1,0,2,1,0] => Output: [0,0,1,1,2]
Time: O(n + k) where k = range | Space: O(k) — optimal when k = O(n)
Radix Sort sorts integers digit by digit from least significant to most significant (LSD radix sort), using a stable sort (counting sort) for each digit.
function radixSort(arr) {
const max = Math.max(...arr);
for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
countingSortByDigit(arr, exp);
}
return arr;
}
function countingSortByDigit(arr, exp) {
const n = arr.length, count = new Array(10).fill(0), output = new Array(n);
for (const n of arr) count[Math.floor(n / exp) % 10]++;
for (let i = 1; i < 10; i++) count[i] += count[i-1];
for (let i = n - 1; i >= 0; i--) {
const digit = Math.floor(arr[i] / exp) % 10;
output[--count[digit]] = arr[i];
}
for (let i = 0; i < n; i++) arr[i] = output[i];
}
// Input: [170,45,75,90,802,24,2,66] => Output: [2,24,45,66,75,90,170,802]
Time: O(d × (n + k)) where d=digits, k=radix | Space: O(n + k)
Randomly select the pivot to reduce the chance of hitting worst-case O(n²) on sorted inputs. Expected performance remains O(n log n).
function randomizedQuickSort(arr, lo = 0, hi = arr.length - 1) {
if (lo >= hi) return arr;
// Random pivot
const pivotIdx = Math.floor(Math.random() * (hi - lo + 1)) + lo;
[arr[pivotIdx], arr[hi]] = [arr[hi], arr[pivotIdx]]; // move to end
// Partition
let p = lo;
for (let i = lo; i < hi; i++) {
if (arr[i] <= arr[hi]) { [arr[p], arr[i]] = [arr[i], arr[p]]; p++; }
}
[arr[p], arr[hi]] = [arr[hi], arr[p]]; // place pivot
randomizedQuickSort(arr, lo, p - 1);
randomizedQuickSort(arr, p + 1, hi);
return arr;
}
// Input: [3,1,4,1,5,9,2,6] => Output: [1,1,2,3,4,5,6,9]
Time: O(n log n) expected, O(n²) worst | Space: O(log n) average
Use a min-heap of size k+1. For a k-sorted array, each element is at most k positions from its correct position. Slide a window of k+1 through the array.
function sortKSortedArray(arr, k) {
// Use a simulated min-heap (sorted slice of size k+1)
const result = [];
const heap = arr.slice(0, k + 1).sort((a, b) => a - b);
for (let i = k + 1; i < arr.length; i++) {
result.push(heap.shift()); // extract min
// Insert arr[i] in sorted position
let j = heap.length;
while (j > 0 && heap[j-1] > arr[i]) { heap[j] = heap[j-1]; j--; }
heap[j] = arr[i];
}
while (heap.length) result.push(heap.shift());
return result;
}
// k=3: [6,5,3,2,8,10,9] => Output: [2,3,5,6,8,9,10]
Time: O(n log k) | Space: O(k)
An inversion is a pair (i,j) where i < j but arr[i] > arr[j]. Count them during merge sort: when right element is picked before left, all remaining left elements form inversions.
function countInversions(arr) {
let count = 0;
function mergeSort(a) {
if (a.length <= 1) return a;
const mid = Math.floor(a.length / 2);
const left = mergeSort(a.slice(0, mid));
const right = mergeSort(a.slice(mid));
const merged = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) { merged.push(left[i++]); }
else { count += left.length - i; merged.push(right[j++]); }
}
return [...merged, ...left.slice(i), ...right.slice(j)];
}
mergeSort(arr);
return count;
}
// Input: [2,4,1,3,5] => Output: 3 ((2,1),(4,1),(4,3))
// Input: [5,4,3,2,1] => Output: 10 (all pairs are inversions)
Time: O(n log n) | Space: O(n)
Use three pointers: low, mid, high. Invariant: arr[0..low-1]=0, arr[low..mid-1]=1, arr[high+1..n-1]=2. Process until mid > high.
function sortColors(nums) {
let low = 0, mid = 0, high = nums.length - 1;
while (mid <= high) {
if (nums[mid] === 0) {
[nums[low], nums[mid]] = [nums[mid], nums[low]];
low++; mid++;
} else if (nums[mid] === 1) {
mid++;
} else {
[nums[mid], nums[high]] = [nums[high], nums[mid]];
high--; // don't increment mid (new nums[mid] is unknown)
}
}
}
// Input: [2,0,2,1,1,0] => Output: [0,0,1,1,2,2]
// Input: [2,0,1] => Output: [0,1,2]
Time: O(n) — single pass | Space: O(1)
QuickSelect is like QuickSort but only recurses into the side that contains the kth element. Average case O(n) because it avoids sorting both halves.
function quickSelect(nums, k) {
// kth largest = index (n-k) in sorted order
function select(arr, lo, hi, target) {
if (lo === hi) return arr[lo];
const pivotIdx = Math.floor(Math.random() * (hi - lo + 1)) + lo;
[arr[pivotIdx], arr[hi]] = [arr[hi], arr[pivotIdx]];
let p = lo;
for (let i = lo; i < hi; i++) {
if (arr[i] <= arr[hi]) { [arr[p], arr[i]] = [arr[i], arr[p]]; p++; }
}
[arr[p], arr[hi]] = [arr[hi], arr[p]];
if (p === target) return arr[p];
if (p < target) return select(arr, p+1, hi, target);
return select(arr, lo, p-1, target);
}
return select(nums, 0, nums.length-1, nums.length - k);
}
// Input: nums=[3,2,1,5,6,4], k=2 => Output: 5
// Input: nums=[3,2,3,1,2,4,5,5,6], k=4 => Output: 4
Time: O(n) average, O(n²) worst | Space: O(1)
TimSort is a hybrid of Insertion Sort and Merge Sort. It exploits natural runs (already-sorted sequences) in real-world data for excellent practical performance.
// TimSort complexity:
// Best: O(n) — already sorted / reverse sorted
// Average: O(n log n)
// Worst: O(n log n)
// Space: O(n) — stable, used in Array.prototype.sort()
// In JavaScript, Array.sort() uses TimSort (V8 engine)
[3,1,4,1,5,9,2,6].sort((a,b) => a-b) // => [1,1,2,3,4,5,6,9]
TimSort is stable and performs well when data has partially sorted regions (common in real data).
Use two stacks: pop from input, insert into sorted output by temporarily moving elements back to input to find the correct position.
function stackSort(arr) {
const sorted = [];
while (arr.length) {
const tmp = arr.pop();
// Move elements from sorted that are greater than tmp back to arr
while (sorted.length && sorted[sorted.length-1] > tmp) {
arr.push(sorted.pop());
}
sorted.push(tmp);
}
return sorted; // sorted[0] = min
}
// Input (as stack, top first): [3,1,4,2] => Output: [1,2,3,4] (min at top)
// Input: [5,1,3,2,4] => Output: [1,2,3,4,5]
Time: O(n²) | Space: O(n)
External Sort is used when data is too large for RAM. Classic approach: External Merge Sort.
// Pseudocode for External Sort:
// Phase 1 — Create sorted runs
for each chunk of data that fits in memory:
load chunk into RAM
sort in memory (e.g., quicksort)
write sorted chunk to disk as "run_i.tmp"
// Phase 2 — k-way merge
open all run files simultaneously
use min-heap: [smallest_value, run_index]
while heap not empty:
extract min, write to output
read next element from same run, push to heap
Complexity: O(n log n) with O(B) memory buffer | Passes: ⌈log_k(n/B)⌉ merge passes where k = number of runs and B = buffer size
Bucket Sort distributes elements into buckets based on value range, sorts each bucket (insertion sort), then concatenates. Works well for uniformly distributed floats in [0,1).
function bucketSort(arr) {
const n = arr.length;
if (!n) return arr;
// Create n empty buckets
const buckets = Array.from({length: n}, () => []);
const min = Math.min(...arr), max = Math.max(...arr);
const range = max - min || 1;
for (const num of arr) {
const idx = Math.floor(((num - min) / range) * (n - 1));
buckets[idx].push(num);
}
const result = [];
for (const bucket of buckets) {
bucket.sort((a, b) => a - b); // insertion sort for small buckets
result.push(...bucket);
}
return result;
}
// Input: [0.78, 0.17, 0.39, 0.26, 0.72, 0.94]
// Output: [0.17, 0.26, 0.39, 0.72, 0.78, 0.94]
Time: O(n + k) average, O(n²) worst | Space: O(n + k)
Pick a pivot, partition the list into three sub-lists (less, equal, greater), recursively sort less and greater, then concatenate.
function quickSortLL(head) {
if (!head || !head.next) return head;
const pivot = head.val;
let lessHead = null, lessTail = null;
let equalHead = null, equalTail = null;
let greaterHead = null, greaterTail = null;
let curr = head;
function append(val, headRef, tailRef) {
const node = { val, next: null };
if (!headRef) { headRef = node; tailRef = node; }
else { tailRef.next = node; tailRef = node; }
return [headRef, tailRef];
}
while (curr) {
if (curr.val < pivot) [lessHead, lessTail] = append(curr.val, lessHead, lessTail);
else if (curr.val === pivot) [equalHead, equalTail] = append(curr.val, equalHead, equalTail);
else [greaterHead, greaterTail] = append(curr.val, greaterHead, greaterTail);
curr = curr.next;
}
const sortedLess = quickSortLL(lessHead);
const sortedGreater = quickSortLL(greaterHead);
if (lessTail) { lessTail.next = equalHead; equalTail.next = sortedGreater; return sortedLess; }
else { equalTail.next = sortedGreater; return equalHead; }
}
// Input: 4->2->8->1->3 => Output: 1->2->3->4->8
Time: O(n log n) average | Space: O(log n) stack