Master comparison and non-comparison sorting algorithms with complexity analysis, optimization techniques, and real-world applications. Includes implementations from Bubble Sort to Timsort.
Sorting Algorithms: Complete Guide
Algorithm Usage in Systems (2023)
1. Comparison Sorts
O(n²) Algorithms
Bubble Sort
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]]; // Swap
}
}
}
return arr;
}Best Case: O(n)
Use When: Educational purposes only
Insertion Sort
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let j = i;
while (j > 0 && arr[j] < arr[j - 1]) {
[arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
j--;
}
}
return arr;
}Best Case: O(n)
Use When: Small or nearly sorted data
O(n log n) Algorithms
Merge Sort
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) {
let result = [];
while (left.length && right.length) {
result.push(left[0] < right[0] ? left.shift() : right.shift());
}
return [...result, ...left, ...right];
}Stable: Yes
Use When: Stable sort needed
Quick 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;
for (let j = low; j < high; j++) {
if (arr[j] < pivot) {
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
}
}
[arr[i], arr[high]] = [arr[high], arr[i]];
return i;
}Space Opt: O(log n)
Use When: General purpose sorting
2. Non-Comparison Sorts
Counting Sort
function countingSort(arr, max = Math.max(...arr)) {
const count = Array(max + 1).fill(0);
const output = Array(arr.length);
// Store count of each element
arr.forEach(num => count[num]++);
// Cumulative count
for (let i = 1; i <= max; i++) {
count[i] += count[i - 1];
}
// Build output array
for (let i = arr.length - 1; i >= 0; i--) {
output[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
return output;
}Range: O(n + k)
Use When: Limited integer range
Radix Sort (LSD)
function radixSort(arr) {
const maxDigits = Math.max(...arr).toString().length;
for (let i = 0; i < maxDigits; i++) {
const buckets = Array.from({ length: 10 }, () => []);
for (const num of arr) {
const digit = getDigit(num, i);
buckets[digit].push(num);
}
arr = [].concat(...buckets);
}
return arr;
}
function getDigit(num, place) {
return Math.floor(Math.abs(num) / Math.pow(10, place)) % 10;
}Stable: Yes
Use When: Large number range
3. Hybrid & Advanced Sorts
Timsort (Python's Default)
// Simplified implementation
function timSort(arr, run = 32) {
// Insertion sort small runs
for (let i = 0; i < arr.length; i += run) {
insertionSort(arr, i, Math.min(i + run - 1, arr.length - 1));
}
// Merge runs
for (let size = run; size < arr.length; size *= 2) {
for (let left = 0; left < arr.length; left += 2 * size) {
const mid = left + size - 1;
const right = Math.min(left + 2 * size - 1, arr.length - 1);
merge(arr, left, mid, right);
}
}
return arr;
}Adaptive: O(n) best case
Used In: Python, Java, Android
Heap Sort
function heapSort(arr) {
// Build max heap
for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
heapify(arr, arr.length, i);
}
// Extract elements
for (let i = arr.length - 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);
}
}In-Place: Yes
Use When: Guaranteed O(n log n) needed
Optimization Techniques
- Introsort: QuickSort + HeapSort fallback (C++ STL)
- Parallel Merge Sort: Divide work across CPU cores
- Block Merge Sort: Cache-friendly variant (Python's Timsort)
- Radix with Counting: Combine for better constant factors
Sorting Algorithm Cheat Sheet
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| QuickSort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| MergeSort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| HeapSort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Radix (LSD) | O(nk) | O(nk) | O(nk) | O(n + k) | Yes |
4. Real-World Applications
Database Indexing
B-Trees: Use insertion sort for small node updates
// Database index maintenance
function updateIndex(records, newRecord) {
records.push(newRecord);
insertionSort(records); // Efficient for small batches
}Big Data Processing
External Sort: Merge sort for disk-based sorting
// MapReduce-style sorting
function externalSort(dataChunks) {
const sortedChunks = dataChunks.map(chunk => mergeSort(chunk));
return kWayMerge(sortedChunks); // Merge sorted chunks
}Graphics Rendering
Depth Sorting: Radix sort for floating-point Z-buffers
function sortTriangles(triangles) {
// Convert float Z to sortable integer
const toSort = triangles.map(t => ({
triangle: t,
key: floatToSortableInt(t.z)
}));
return radixSort(toSort).map(x => x.triangle);
}Sorting Algorithm Selection Guide
✓ Small datasets (<100 items): Insertion Sort
✓ General purpose: QuickSort (with randomization)
✓ Stable requirement: MergeSort or Timsort
✓ Fixed-range integers: Counting/Radix Sort
✓ Memory constrained: HeapSort
Pro Tip: Modern systems use hybrid algorithms like Timsort (MergeSort + InsertionSort) and Introsort (QuickSort + HeapSort) to handle real-world data patterns efficiently. Always benchmark with your actual data.
0 Interaction
0 Views
0 Likes
×
