Sorting Algorithm Step Counter
Compare operation counts for bubble, insertion, selection, merge, and quicksort.
Enter array size n to see step estimates and Big-O efficiency class.
Sorting Algorithm Complexity
Sorting is one of the most studied problems in computer science. The efficiency of a sorting algorithm is measured by how many operations it performs as input size n grows. This calculator shows estimated operation counts for five fundamental algorithms.
Time Complexity Summary
| Algorithm | Best Case | Average Case | Worst Case | Space | Stable |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
How the estimates are calculated:
- Bubble Sort: n × (n-1) / 2 comparisons on average
- Insertion Sort: n × (n-1) / 4 on average — roughly half of bubble sort
- Selection Sort: n × (n-1) / 2 always — no early exit optimization
- Merge Sort: n × log₂(n) operations consistently at every input size
- Quicksort: n × log₂(n) × 1.39 on average with a random pivot strategy
The n² vs n log n divide
For small arrays (n under 20), the simpler O(n²) algorithms are often faster in practice due to lower constant-factor overhead. At n = 100, the performance difference becomes visible. At n = 10,000, merge sort performs roughly 100 times fewer operations than bubble sort. At n = 1,000,000, the gap exceeds 50,000 times — making the choice of algorithm critical.
Stable vs unstable sorts
A stable sort preserves the original order of equal elements. Bubble, insertion, and merge sort are stable. Selection sort and standard quicksort are not — they may reorder equal elements.
Practical guidance
- Nearly sorted data: insertion sort is O(n) in the best case — very fast on presorted input.
- Need guaranteed O(n log n): use merge sort. Quicksort degrades to O(n²) on sorted input without randomization.
- Memory constrained: avoid merge sort (it needs O(n) extra space). Quicksort needs only O(log n).
- In production: most standard libraries use Timsort (merge + insertion hybrid) or Introsort (quicksort + heapsort fallback), which automatically adapt to input patterns.