The above graph compares performance of several different sorting algorithms implemented in C++. X-axis is the array size being sorted. Y-axis is the time in seconds it took to sort the array. The faster the algorithm, the less time it takes to sort. The above graph is for arrays filled with uniformly distributed random unsigned 32-bit integers.
See the link below to explore interactively the above graph in detail. As you scroll through the graph, individual performance data points are shown, with array size and run time in seconds for each of the C++ sorting algorithms:
- In-place Merge sort is the slowest of the algorithms at 1.6 Million integers/second
- STL heap sort is the next slowest: sorting at 3 Million
- Qsort is faster at about 4 Million
- Merge sort is only slightly slower than STL sort, at 6.6 Million
- Standard STL sort processes at 7.1 Million integers/second
- MSD Radix sort is the second fastest algorithm: about 2X slower than LSD Radix sort, at 24 Million
- LSD Radix sort is the fastest algorithm, sorting at 57.4 Million integers/second: 8X faster than STL sort, 19X faster than STL Heap sort, and 36X faster than in-place Merge sort
Heap sort and in-place Merge sort have the highest variations in performance.