Algorithms
Sorting Algorithms
Implement and understand the classic sorting algorithms and when to use each.
Sorting Algorithm Comparison
| Algorithm | Best | Average | 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 |
In Practice
- JavaScript's built-in
Array.sort(): Use this in production - Merge sort: Great for linked lists, stable
- Quick sort: Fast in practice, common in language implementations
- Insertion sort: Best for nearly-sorted or small arrays
Example
javascript
// Merge Sort - O(n log n) - stable, works well
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, ...left.slice(i), ...right.slice(j)];
}
// Quick Sort - O(n log n) average
function quickSort(arr, low = 0, high = arr.length - 1) {
if (low < high) {
const pivotIdx = partition(arr, low, high);
quickSort(arr, low, pivotIdx - 1);
quickSort(arr, pivotIdx + 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;
}
// Insertion Sort - O(n) for nearly sorted
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(mergeSort([5, 3, 8, 1, 9, 2])); // [1, 2, 3, 5, 8, 9]Try it yourself — JAVASCRIPT