Algorithm Sorting Comparison Calculator
Compare the estimated operation counts and space usage of common sorting algorithms for a given array size n.
Results will appear here.
Formulas (Operation Counts)
Bubble / Selection Sort: O(n²) — Best: n, Avg/Worst: n²
Insertion Sort: Best: n, Avg: n²/2, Worst: n²
Merge Sort: Θ(n log₂ n) all cases; Space: O(n)
Quick Sort: Best/Avg: n log₂ n, Worst: n² (bad pivot); Space: O(log n) stack
Heap Sort: Θ(n log₂ n) all cases; Space: O(1)
Counting Sort: Θ(n + k) all cases; Space: O(n + k)
Radix Sort (base 10): Θ(d·(n + 10)) where d = ⌈log₁₀(k+1)⌉; Space: O(n + 10)
Wall-clock estimate assumes 10⁸ operations per second.
Assumptions & References
- Operation counts represent comparisons or element moves (dominant term).
- Quick Sort average case assumes random pivot selection (expected n log n).
- Counting Sort and Radix Sort assume non-negative integer keys with max value k.
- Radix Sort digit count: d = ⌈log₁₀(k + 1)⌉, base b = 10.
- Space complexity is auxiliary space only (not including input array).
- Wall-clock time is a rough estimate; real performance depends on hardware, cache, and implementation.
- Reference: Cormen et al., Introduction to Algorithms (CLRS), 4th ed.
- n is limited to 10,000,000 for display clarity; complexities remain valid beyond this.