Sorting Algorithms
Arrange data in order
What is it?
Sorting means putting things in order ā like arranging books on a shelf from A to Z, or ranking students by score.
Different algorithms trade off speed, memory, and stability (whether equal items keep their original order).
Algorithm Comparison
| Algorithm | Best | Average | Worst | Space | Stable | |----------------|------------|------------|------------|----------|--------| | Bubble Sort | O(n) | O(nĀ²) | O(nĀ²) | O(1) | ā Yes | | Insertion Sort | O(n) | O(nĀ²) | O(nĀ²) | O(1) | ā Yes | | Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | ā Yes | | Quick Sort | O(n log n) | O(n log n) | O(nĀ²) | O(log n) | ā No | | Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | ā No |
Real-World Examples
Code Example
What this code shows
Merge sort splits [3,1,4,1,5,9,2] into single-element halves (already sorted), then merges them back together in order ā always comparing the front of the left and right half and picking the smaller one.
function mergeSort(arr) {
// base case: a single item is already sorted
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid)); // sort left half
const right = mergeSort(arr.slice(mid)); // sort right half
// merge two sorted halves into one sorted array
const result = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
// always pick the smaller front element
result.push(left[i] <= right[j] ? left[i++] : right[j++]);
}
// append any remaining elements
return result.concat(left.slice(i), right.slice(j));
}
console.log(mergeSort([3, 1, 4, 1, 5, 9, 2]));
// [1, 1, 2, 3, 4, 5, 9]Expected Output
[1, 1, 2, 3, 4, 5, 9]