20. Practical Comparison of O(N²) Sorts
While Bubble, Selection, and Insertion Sort all share the worst-case O(N²) time complexity, their performance characteristics differ in practice.
| Algorithm | Worst Case Time | Best Case Time | Swaps/Shifts | Stability |
|---|---|---|---|---|
| Bubble Sort | O(N²) | O(N) | Many swaps/shifts | Stable |
| Selection Sort | O(N²) | O(N²) | Minimum swaps | Unstable |
| Insertion Sort | O(N²) | O(N) | Many shifts, few swaps | Stable |
- Stability: A sort is stable if it preserves the relative order of equal elements.
- When to Use Insertion Sort: It is the most practical of the O(N²) sorts because its O(N) best-case performance makes it very fast for arrays that are already mostly sorted.
- When NOT to Use: For large, completely unsorted datasets, we must move to more advanced O(N log N) algorithms.