🔃 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 (avg) | Time (worst) | Space | Stable? |
|---|---|---|---|---|
| Bubble Sort | O(n²) | O(n²) | O(1) | Yes |
| Selection Sort | O(n²) | O(n²) | O(1) | No |
| Insertion Sort | O(n²) | O(n²) | O(1) | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n) | Yes |
| Quick Sort | O(n log n) | O(n²) | O(log n) | No |
| Heap Sort | O(n log n) | O(n log n) | O(1) | No |
| Counting Sort | O(n + k) | O(n + k) | O(k) | Yes |
| Radix Sort | O(nk) | O(nk) | O(n+k) | Yes |
Cyclic Sort: for arrays containing numbers in range [1..n] — place each number at index num-1 in O(n), O(1) space.
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;
}
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