DSA, Database System & Operating System — Sorting, Searching, and Graphs, NEC licence examination syllabus (Nepal Engineering Council).
Every sorting algorithm you've just learned, side by side, ready for direct comparison.
| Algorithm | Best | Average | Worst |
|---|---|---|---|
| Insertion | O(n) | O(n²) | O(n²) |
| Selection | O(n²) | O(n²) | O(n²) |
| Bubble | O(n) | O(n²) | O(n²) |
| Merge | O(n log n) | O(n log n) | O(n log n) |
| Heap | O(n log n) | O(n log n) | O(n log n) |
| Radix | O(nk) | O(nk) | O(nk) |
Slide n down to 8 and up to 100 — the two curves cross at n = 16, where both cost exactly 64.
Big-O deliberately discards constant factors, and that is exactly what makes it misleading at small n. An O(n²) algorithm with a small constant beats an O(n log n) one with a large constant on small inputs — every time, not occasionally.
This is not a theoretical curiosity. Real sorting libraries are hybrid: they run quicksort or merge sort down to partitions of roughly ten to twenty elements, then switch to insertion sort for the rest. The switch exists precisely because below the crossover the "worse" algorithm is genuinely faster.SpaceMerge sort needs O(n) extra memory; heap sort and quicksort sort in place. On large data this can matter more than speed.
StabilityWhether equal elements keep their original relative order. Merge and insertion sort are stable; heap and quick sort are not.
Worst vs averageQuicksort averages O(n log n) but degrades to O(n²) on bad pivots. Merge and heap sort are O(n log n) in the worst case too.
AdaptivityInsertion sort runs in O(n) on already-sorted data. Most others do not care about the initial order.
A full-credit answer names the complexity and the trade-off. "Merge sort, because it is O(n log n) in the worst case and stable, at the cost of O(n) extra space" says more than the notation alone ever can.
Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.
Loading…