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.
How we build and check this calculator
This calculator runs entirely in your browser, so the numbers you enter stay on your device. The math behind it is written by hand and tested against worked examples and standard references before the page goes live.
SuperGlobalCalculator is independently built and maintained. See how we build and verify our calculators.