| Bubble Sort |
Repeatedly compares adjacent elements and swaps them if wrong order. Largest element "bubbles" to end each pass. |
Educational purposes, tiny arrays |
Teaching concepts, checking if already sorted |
| Selection Sort |
Finds minimum from unsorted part, swaps with first unsorted element. Builds sorted region from left. |
Small arrays, minimize swaps |
Systems where write operations are expensive (only n-1 swaps) |
| Insertion Sort |
Takes each element and inserts into correct position in sorted portion. Like sorting cards in hand. |
Small/nearly sorted data |
Arrays < 50 elements, nearly sorted data, part of Timsort/Introsort |
| Merge Sort |
Divide array in half recursively, sort halves, merge sorted halves together. |
Large data, need stability |
Guaranteed O(n log n), linked lists, external sorting, parallel processing |
| Quick Sort |
Pick pivot, partition around it (smaller left, larger right), recursively sort partitions. |
General purpose sorting |
Default choice for arrays, cache-friendly, average case excellent |
| Heap Sort |
Build max heap, repeatedly extract max and rebuild heap with remaining elements. |
Need O(n log n) + O(1) space |
Space-constrained systems, real-time systems, priority queues |
| Counting Sort |
Count occurrences of each value, use counts to place elements in sorted order. |
Integer sorting, small range |
Sorting integers 0-100, when k ≈ n, as subroutine in Radix Sort |
| Radix Sort |
Sort digit by digit from least to most significant, using stable sort for each digit. |
Fixed-length integers/strings |
Sorting IDs, phone numbers, fixed-length strings, multiple keys |
| Bucket Sort |
Distribute elements into buckets, sort buckets individually, concatenate results. |
Uniformly distributed data |
Floating points in [0,1), uniformly distributed data |
| Shell Sort |
Generalized insertion sort with gap sequences. Sorts elements far apart first, reduces gap. |
Medium-sized arrays |
Better than insertion for medium data, embedded systems (simple code) |
| Tim Sort |
Hybrid of Merge + Insertion. Identifies runs, uses insertion for small runs, merges runs. |
Real-world data with patterns |
Python/Java default, real-world data (often partially sorted) |
