C++ Sorting Algorithms

SortingAlgorithmPerformance

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:

Interactive Graph of Sorting Algorithms: Time vs. Array Size

Standard STL sort is able to sort 7.1 Million integers per second, while STL heap sort can sort 3 Million. LSD Radix sort is the fastest algorithm, able to sort 57.4 Million integers – 8X faster than STL sort and 19X faster than STL Heap sort. MSD Radix sort is the second fastest algorithm – slightly more than 2X slower than LSD Radix sort. Merge sort is only slightly slower than STL sort. In-place Merge sort is the slowest of the algorithms. Heap sort and in-place Merge sort have the highest variations in performance.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s