Sorting Algorithms
A comprehensive guide to understanding how different sorting algorithms work, their time complexities, and when to use each one.
Introduction
Sorting is one of the most fundamental operations in computer science. A sorting algorithm arranges elements in a specific order, typically ascending or descending. Understanding these algorithms is crucial for:
- Building efficient applications
- Preparing for technical interviews
- Understanding algorithm design principles
- Choosing the right tool for specific problems
Bubble Sort
How It Works
Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they're in the wrong order. The pass through the list is repeated until no swaps are needed.
function bubbleSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
for (let j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap elements
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}Selection Sort
How It Works
Selection Sort divides the array into sorted and unsorted parts. It repeatedly selects the minimum element from the unsorted part and moves it to the beginning of the unsorted part.
function selectionSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
let minIdx = i;
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
if (minIdx !== i) {
[arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
}
}
return arr;
}Insertion Sort
How It Works
Insertion Sort builds the sorted array one element at a time. It picks each element and inserts it into its correct position in the already sorted part of the array.
function insertionSort(arr) {
const n = arr.length;
for (let i = 1; i < n; i++) {
let 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;
}Quick Sort
How It Works
Quick Sort uses divide-and-conquer. It selects a 'pivot' element and partitions the array around it, placing smaller elements before and larger elements after the pivot, then recursively sorts the sub-arrays.
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;
}Merge Sort
How It Works
Merge Sort divides the array into halves, recursively sorts them, and then merges the sorted halves. It's a stable, divide-and-conquer algorithm with consistent O(n log n) performance.
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));
}Algorithm Comparison
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| 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) | |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
When to Use Which?
- Small arrays (n < 50): Insertion Sort - simple and efficient
- Nearly sorted data: Insertion Sort - O(n) best case
- General purpose: Quick Sort - excellent average performance
- Need stability: Merge Sort - consistent O(n log n)
- Limited memory: Heap Sort or Quick Sort - O(1) or O(log n) space