Comprehensive collection of sorting algorithms with definitions, properties, code, proofs, examples, and variants.
Key properties to compare algorithms:
-
Stability
- Stable: maintains relative order of equal elements.
- Unstable: may change the relative order of equal elements.
-
Recursive vs. Iterative
- Recursive: uses recursive calls (e.g., Merge Sort, Quick Sort).
- Iterative: uses loops (e.g., Bubble Sort, Selection Sort).
-
Adaptive vs. Non-Adaptive
- Adaptive: benefits from partial order (e.g., Insertion Sort, TimSort).
- Non-Adaptive: doesn’t leverage existing order (e.g., Selection Sort).
-
Internal vs. External
- Internal: data fits into memory (most algorithms here).
- External: for data larger than memory (e.g., External Merge Sort).
-
In-place vs. Out-of-place
- In-place: O(1) or O(log n) extra memory (e.g., Quick Sort, Heap Sort).
- Out-of-place: requires additional arrays/buffers (e.g., Merge Sort, Counting Sort).
For details, code, complexity analysis, and proofs, open each algorithm page above.
| Algorithm | Stable | In-place | Best | Average | Worst | Space | Notes |
|---|---|---|---|---|---|---|---|
| Bubble Sort | Yes | Yes | O(n) | O(n^2) | O(n^2) | O(1) | Early-exit optimization makes best-case linear |
| Selection Sort | No | Yes | O(n^2) | O(n^2) | O(n^2) | O(1) | Minimal swaps |
| Insertion Sort | Yes | Yes | O(n) | O(n^2) | O(n^2) | O(1) | Adaptive to low inversions |
| Merge Sort | Yes | No | O(n log n) | O(n log n) | O(n log n) | O(n) | External-friendly |
| Quick Sort | No | Yes | O(n log n) | O(n log n) | O(n^2) | O(log n) avg | Random/median-of-three pivot reduces worst cases |
| Heap Sort | No | Yes | O(n log n) | O(n log n) | O(n log n) | O(1) | Selection via heap |
| Shell Sort | No | Yes | Varies | Varies | ~O(n^(3/2))–O(n^2) | O(1) | Performance depends on gap sequence |
| Counting Sort | Yes | No | O(n+k) | O(n+k) | O(n+k) | O(n+k) | Keys in small integer range |
| Radix Sort | Yes | No | O((n+b)d) | O((n+b)d) | O((n+b)d) | O(n+b) | Uses stable subroutine; integers/strings |
| Bucket Sort | Depends | No | ~O(n) | ~O(n) | O(n^2) | O(n+k) | Assumes near-uniform keys |
| Pigeonhole Sort | Yes | No | O(n+k) | O(n+k) | O(n+k) | O(n+k) | Range close to n |
| TimSort | Yes | No | O(n) | O(n log n) | O(n log n) | O(n) | Python/Java default sort |
| IntroSort | No | Yes | O(n log n) | O(n log n) | O(n log n) | O(log n) | Quicksort + Heapsort fallback |
| Smoothsort | No | Yes | O(n) | O(n log n) | O(n log n) | O(1) | Adaptive heapsort variant |
| Patience Sorting | Can be | No | O(n log n) | O(n log n) | O(n log n) | O(n) | Connected to LIS |
| Bitonic Sort | No | Varies | O(n log^2 n) | O(n log^2 n) | O(n log^2 n) | O(1) | Parallel sorting network |
- Each algorithm page links to Python (
.py), C (.c), and C++ (.cpp) sources under the matching folder, e.g.,algorithms/comparison-based/code/quick_sort.*. - Python: run files directly with your interpreter.
- C/C++: compile with your preferred compiler (clang/gcc). Example commands:
# Python
python3 algorithms/comparison-based/code/quick_sort.py
# C
cc -O2 -std=c11 -o quick_sort algorithms/comparison-based/code/quick_sort.c && ./quick_sort
# C++
c++ -O2 -std=c++17 -o quick_sort_cpp algorithms/comparison-based/code/quick_sort.cpp && ./quick_sort_cppNote: Some advanced algorithms (like Smoothsort) include simplified or stub implementations with clear notes in their pages.