🔃 Sorting
One-line summary: Rearrange elements in order — the prerequisite for binary search, two pointers, and many greedy algorithms.
Enhanced Visualization
Interactive comparison of Bubble Sort, Quick Sort, and Merge Sort with real-time performance metrics
Algorithm Analysis
The enhanced animation above demonstrates three fundamental sorting paradigms:
🔴 Bubble Sort - Simple but Inefficient
- Strategy: Compare adjacent elements and swap if out of order
- Performance: ~500,000 operations for n=1000 elements
- Visual: Watch elements "bubble" to their correct positions
- Best for: Educational purposes, very small datasets
🟣 Quick Sort - Efficient Divide-and-Conquer
- Strategy: Choose pivot, partition around it, recursively sort
- Performance: ~10,000 operations for n=1000 elements
- Visual: See pivot selection and partitioning phases
- Best for: General-purpose sorting, in-place requirements
🔵 Merge Sort - Stable and Predictable
- Strategy: Divide array, sort halves, merge sorted results
- Performance: ~10,000 operations for n=1000 elements
- Visual: Observe divide-and-conquer with merging phases
- Best for: Stable sorting, linked lists, external sorting
Complete Algorithm Comparison
| Algorithm | Time (best) | Time (avg) | Time (worst) | Space | Stable? | When to Use |
|---|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Teaching only; nearly-sorted tiny arrays |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No | Minimizing number of swaps |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Small or nearly-sorted data; online sorting |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | Stable sort; linked lists; external sorting |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | General-purpose, in-place, cache-friendly |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Guaranteed O(n log n) with O(1) space |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(k) | Yes | Small integer range k |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n+k) | Yes | Fixed-width integers/strings |
k = range of input values (counting) or number of digits (radix). Stable = equal elements keep their original relative order.
Cyclic Sort: for arrays containing numbers in range [1..n] — place each number at index num-1 in O(n), O(1) space.
🧭 Which Sort Should I Use?
flowchart TD
A["Need to sort?"] --> B{"Small input\n(n < 50) or\nnearly sorted?"}
B -->|Yes| C["Insertion Sort"]
B -->|No| D{"Values are\nsmall integers?"}
D -->|Yes| E["Counting / Radix Sort\nO(n+k)"]
D -->|No| F{"Need stability?"}
F -->|Yes| G["Merge Sort\nO(n log n), O(n)"]
F -->|No| H{"Memory constrained?"}
H -->|Yes| I["Heap Sort\nO(n log n), O(1)"]
H -->|No| J["Quick Sort\navg O(n log n), in-place"]
Stability — Why It Matters
A stable sort preserves the relative order of records with equal keys. This is essential when sorting by multiple criteria (e.g., sort by name, then stably by age). Merge, insertion, counting, and radix sorts are stable; quick, heap, and selection sorts are not.
Common Patterns
Merge Sort
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
return merge(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid)));
}
function merge(left, right) {
const result = [];
let i = 0,
j = 0;
while (i < left.length && j < right.length)
result.push(left[i] <= right[j] ? left[i++] : right[j++]);
return result.concat(left.slice(i), right.slice(j));
}
Cyclic Sort
function cyclicSort(nums) {
let i = 0;
while (i < nums.length) {
const correct = nums[i] - 1;
if (nums[i] !== nums[correct]) [nums[i], nums[correct]] = [nums[correct], nums[i]];
else i++;
}
return nums;
}
Quick Sort (in-place, Lomuto partition)
function quickSort(arr, lo = 0, hi = arr.length - 1) {
if (lo >= hi) return arr;
const pivot = arr[hi];
let i = lo;
for (let j = lo; j < hi; j++) {
if (arr[j] < pivot) {
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
}
}
[arr[i], arr[hi]] = [arr[hi], arr[i]]; // place pivot
quickSort(arr, lo, i - 1);
quickSort(arr, i + 1, hi);
return arr;
}
// Avg O(n log n); randomize the pivot to avoid the O(n^2) worst case.
Insertion Sort (great for small / nearly-sorted arrays)
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--];
arr[j + 1] = key;
}
return arr;
}
// O(n) on nearly-sorted input, O(n^2) worst case. Stable and in-place.
📚 Implementations: Full, tested implementations of each algorithm live alongside this guide under
concepts/sorting/. Study the comparison table above, then read the code for the algorithm you need.
Pitfalls
- Quick sort worst case O(n²) on sorted input — use random pivot or 3-way partition
- Stable vs unstable: use stable sort when equal elements must maintain relative order
- JS
Array.sort()is not guaranteed stable in older engines (ES2019+ guarantees it)
Practice Problems
Related Topics
- Binary Search — requires sorted input
- Two Pointers — converging pointers need sorted array
- Heap — heapsort; partial sort for Top-K
← Back to Home · © sparshjaswal