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

  • 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.

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