Time complexities of sorting algorithms are visualized via matplotlib.pyplot
Comparison sorts that are Quicksort, Merge sort and Heapsort; non-comparison sorts that are LSD Radix Sort and Counting Sort are tested based on the sizes of randomly shuffled arrays.
Among the comparison sorts, Quicksort was the fastest one on average. The reason of the faster sorting is that Quicksort doesn't do unnecessary element swaps compared to Merge sort and Heapsort. However, there remains the chance of worst-case performance which is O(N2) time. By randomly choosing the pivot, I tried to avoid worst cases of Quicksort.
A comparison sort cannot perform better than O(N logN) on average.
| Best-case | Average-case | Worst-case | |
|---|---|---|---|
| Quicksort | O(N logN) | O(N logN) | O(N2) |
| Merge sort | O(N logN) | O(N logN) | O(N logN) |
| Heapsort | O(N logN) | O(N logN) | O(N logN) |
Between LSD Radix Sort with Base 10 and Counting sort, Counting sort performed better on the arrays with bigger size.
Non-comparison sorts are not limited to Ω(N logN). In the table below, r is the range of numbers to be sorted, k is the size of the keys and d is the digit size.
| Best-case | Average-case | Worst-case | |
|---|---|---|---|
| LSD Radix Sort | O(N) | O(N ⋅ k⁄d) | O(N ⋅ k⁄d) |
| Counting sort | O(N) | O(N + r) | O(N + r) |
Zoom in on chart:
