| Adaptive Sort | O(n log n) | O(log n) | no | no | Reads the data before sorting: counting sort for integer ranges, insertion sort for tiny or nearly-sorted inputs, introsort with heapsort fallback otherwise. |
| Bubble Sort | O(n²) | O(1) | yes | no | Compares adjacent pairs and swaps them if out of order. Each pass settles the largest remaining element. |
| Bucket Sort | O(n+k) | O(n) | yes | no | Scatters elements into buckets, sorts each bucket with insertion sort, then concatenates. |
| Cocktail Sort | O(n²) | O(1) | yes | no | Bidirectional bubble sort — forward pass pushes the max right, backward pass pushes the min left. Faster on partially-sorted data. |
| Comb Sort | O(n²) | O(1) | no | no | Eliminates turtles (small values near the end) by comparing elements far apart. Shrinks the gap by factor 1.3 each pass. |
| Counting Sort | O(n+k) | O(k) | yes | no | Tallies occurrences of each integer and reconstructs the array. Requires a bounded key range. |
| Cycle Sort | O(n²) | O(1) | no | no | Writes each element exactly once by tracing permutation cycles. Optimal when array writes are expensive. |
| Gnome Sort | O(n²) | O(1) | yes | yes | A single pointer advances if neighbors are in order, or swaps and retreats. The simplest possible sorting algorithm. |
| Heap Sort | O(n log n) | O(1) | no | no | Builds a max-heap, then repeatedly extracts the max to produce sorted output in-place. |
| Insertion Sort | O(n²) | O(1) | yes | yes | Inserts each element into its correct spot in the already-sorted prefix. Fast on nearly-sorted data. |
| Introsort | O(n log n) | O(log n) | no | no | Quicksort with a safety net: if recursion depth exceeds 2·log₂n, it falls back to heapsort. Small subarrays finish with insertion sort. The basis of std::sort. |
| Logos Sort | O(n log n) | O(log n) | no | no | Nine strategies applied in order: tally, gallop, cut at the golden ratio, consult three voices, roll the die, divide into three, recurse the small. |
| Merge Sort | O(n log n) | O(n) | yes | no | Recursively divides in half, sorts each half, then merges. Guaranteed O(n log n) in all cases. |
| Odd-Even Sort | O(n²) | O(1) | yes | no | Alternates between odd-indexed and even-indexed adjacent swaps. Parallelizes naturally — each phase can run simultaneously. |
| Pancake Sort | O(n²) | O(1) | no | no | Sorts by prefix reversals only — like flipping stacks of pancakes. Each round places the next-largest element using at most 2 flips. |
| Quick Sort | O(n log n) | O(log n) | no | no | Picks a pivot, partitions around it, and recurses on both sides. O(n log n) average; O(n²) worst case. |
| Radix Sort | O(nk) | O(n+k) | yes | no | Sorts digit by digit, least to most significant, using counting sort at each position. |
| Selection Sort | O(n²) | O(1) | no | no | Finds the minimum of the unsorted region and swaps it to the sorted boundary. O(n) swaps total. |
| Shell Sort | O(n log² n) | O(1) | no | no | Insertion sort over a shrinking gap — long-range swaps first, fine-tuning last. |
| Tim Sort | O(n log n) | O(n) | yes | no | Detects natural runs, extends short ones with insertion sort, then merges via galloping mode. Python's and Java's built-in sort. |