Sorting is one of the most fundamental operations in computer science. This guide covers all essential sorting algorithms with implementations and analysis.
Why Learn Sorting Algorithms? #
- Interview staple - Frequently asked
- Foundation - Understanding algorithm design
- Practical - Used everywhere in software
- Optimization - Learn time/space tradeoffs
Bubble Sort #
Repeatedly swap adjacent elements if they’re in wrong order.
function bubbleSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
let swapped = false;
for (let j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
swapped = true;
}
}
if (!swapped) break; // Already sorted
}
return arr;
}
console.log(bubbleSort([64, 34, 25, 12, 22, 11, 90]));
// [11, 12, 22, 25, 34, 64, 90]
Time: O(n²), Space: O(1) Stable: Yes
Selection Sort #
Find minimum element and place it at beginning.
function selectionSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex !== i) {
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
}
return arr;
}
console.log(selectionSort([64, 25, 12, 22, 11]));
// [11, 12, 22, 25, 64]
Time: O(n²), Space: O(1) Stable: No
Insertion Sort #
Build sorted array one element at a time.
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;
}
console.log(insertionSort([12, 11, 13, 5, 6]));
// [5, 6, 11, 12, 13]
Time: O(n²), Space: O(1) Stable: Yes Best for: Small arrays, nearly sorted data
Merge Sort #
Divide and conquer: split, sort, merge.
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) {
if (left[i] <= right[j]) {
result.push(left[i++]);
} else {
result.push(right[j++]);
}
}
return result.concat(left.slice(i)).concat(right.slice(j));
}
console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));
// [3, 9, 10, 27, 38, 43, 82]
Time: O(n log n), Space: O(n) Stable: Yes Best for: Linked lists, stable sorting needed
Quick Sort #
Choose pivot, partition, recursively sort.
function quickSort(arr, low = 0, high = arr.length - 1) {
if (low < high) {
const pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
return arr;
}
function partition(arr, low, high) {
const pivot = arr[high];
let i = low - 1;
for (let j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
return i + 1;
}
console.log(quickSort([10, 7, 8, 9, 1, 5]));
// [1, 5, 7, 8, 9, 10]
Time: O(n log n) average, O(n²) worst, Space: O(log n) Stable: No Best for: General purpose, in-place sorting
Heap Sort #
Build max heap, extract maximum repeatedly.
function heapSort(arr) {
const n = arr.length;
// Build max heap
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// Extract elements from heap
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;
const left = 2 * i + 1;
const right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
heapify(arr, n, largest);
}
}
console.log(heapSort([12, 11, 13, 5, 6, 7]));
// [5, 6, 7, 11, 12, 13]
Time: O(n log n), Space: O(1) Stable: No Best for: When space is limited
Counting Sort #
Count occurrences of each value.
function countingSort(arr) {
const max = Math.max(...arr);
const min = Math.min(...arr);
const range = max - min + 1;
const count = new Array(range).fill(0);
const output = new Array(arr.length);
// Count occurrences
for (const num of arr) {
count[num - min]++;
}
// Cumulative count
for (let i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
// Build output
for (let i = arr.length - 1; i >= 0; i--) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
return output;
}
console.log(countingSort([4, 2, 2, 8, 3, 3, 1]));
// [1, 2, 2, 3, 3, 4, 8]
Time: O(n + k), Space: O(k) Stable: Yes Best for: Small range of integers
Radix Sort #
Sort by individual digits.
function radixSort(arr) {
const max = Math.max(...arr);
const maxDigits = String(max).length;
for (let k = 0; k < maxDigits; k++) {
const buckets = Array.from({ length: 10 }, () => []);
for (const num of arr) {
const digit = getDigit(num, k);
buckets[digit].push(num);
}
arr = [].concat(...buckets);
}
return arr;
}
function getDigit(num, place) {
return Math.floor(Math.abs(num) / Math.pow(10, place)) % 10;
}
console.log(radixSort([170, 45, 75, 90, 802, 24, 2, 66]));
// [2, 24, 45, 66, 75, 90, 170, 802]
Time: O(d × n), Space: O(n + k) Stable: Yes Best for: Fixed-length integers
Bucket Sort #
Distribute elements into buckets, sort each.
function bucketSort(arr, bucketSize = 5) {
if (arr.length === 0) return arr;
const min = Math.min(...arr);
const max = Math.max(...arr);
const bucketCount = Math.floor((max - min) / bucketSize) + 1;
const buckets = Array.from({ length: bucketCount }, () => []);
// Distribute into buckets
for (const num of arr) {
const index = Math.floor((num - min) / bucketSize);
buckets[index].push(num);
}
// Sort each bucket and concatenate
return buckets.reduce((sorted, bucket) => {
return sorted.concat(bucket.sort((a, b) => a - b));
}, []);
}
console.log(bucketSort([0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]));Time: O(n + k), Space: O(n + k) Stable: Yes Best for: Uniformly distributed data
Comparison of Sorting Algorithms #
| Algorithm | Time (Best) | Time (Average) | Time (Worst) | Space | Stable |
|---|---|---|---|---|---|
| Bubble | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | No |
| Insertion | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Counting | O(n + k) | O(n + k) | O(n + k) | O(k) | Yes |
| Radix | O(d × n) | O(d × n) | O(d × n) | O(n + k) | Yes |
| Bucket | O(n + k) | O(n + k) | O(n²) | O(n + k) | Yes |
Which Sort to Use? #
General purpose: Quick Sort or Merge Sort Nearly sorted: Insertion Sort Small arrays: Insertion Sort Stable sort needed: Merge Sort Space limited: Heap Sort or Quick Sort Integer range known: Counting Sort Fixed-length integers: Radix Sort
JavaScript Built-in Sort #
const arr = [3, 1, 4, 1, 5, 9, 2, 6];
// Default (lexicographic)
arr.sort(); // Wrong for numbers!
// Numeric sort
arr.sort((a, b) => a - b); // Ascending
arr.sort((a, b) => b - a); // Descending
// Custom comparator
const users = [
{ name: 'Alice', age: 25 },
{ name: 'Bob', age: 20 }
];
users.sort((a, b) => a.age - b.age);Stability in Sorting #
A sort is stable if equal elements maintain their relative order.
const data = [
{ name: 'Alice', score: 90 },
{ name: 'Bob', score: 90 },
{ name: 'Charlie', score: 85 }
];
// Stable sort preserves Alice before Bob
data.sort((a, b) => a.score - b.score);
// Alice still appears before Bob (both score 90)
Custom Sorting Examples #
Sort by Multiple Criteria #
users.sort((a, b) => {
if (a.age !== b.age) {
return a.age - b.age;
}
return a.name.localeCompare(b.name);
});Sort Strings Ignoring Case #
strings.sort((a, b) => a.toLowerCase().localeCompare(b.toLowerCase()));Sort by Date #
events.sort((a, b) => new Date(a.date) - new Date(b.date));Sorting algorithms are fundamental to computer science. Understanding their tradeoffs helps you choose the right algorithm for your needs.