| Algorithm | Best | Average | Worst | Auxiliary Space | Core Idea |
|---|---|---|---|---|---|
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Grow a sorted prefix |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Split → sort → merge |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) average recursion | Partition around a pivot |
| Bubble Sort | O(n)* | O(n²) | O(n²) | O(1) | Swap adjacent inversions |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | Repeatedly select the minimum |
* Bubble sort has O(n) best-case only when implemented with an early-exit check. In-place quicksort typically uses O(log n) recursion space on average, while the simple Python version that constructs separate left/right lists uses O(n) additional memory.