Sorting Speed of Several Languages

Most computer programming languages provide built-in standard sorting algorithms. Let’s compare performance of these.

C++ Sorting

C++SpeedOfSortingIntegers

The above graph shows performance of the standard C++ STL sort algorithm. The vertical axis is time measured in seconds. The horizontal axis is array size of integers (32-bits each). Signed 32-bit integer values in the array are random with a uniform distribution. Performance measurements were done on an Intel i5-6300HQ quad-core laptop processor. This algorithm is non-parallel – used a single core out of the four available cores in this processor. For instance, it took C++ STL sort algorithm about 14 seconds to sort an array of 100 Million 32-bit integers. Standard C++ STL sort is able to sort 7.1 Million 32-bit integers per second.

JavaScript Sorting

JavaScript provides a standard sorting algorithm (possibly Merge Sort), which sorts integers as strings when a comparison function has not been provided, which does not produce correct results for sorting integers. JavaScript sort can sort integers when the programmer provides a simple comparison function that subtracts the two integers. The graph below shows performance of JavaScript sort on the Intel i5-6300HQ quad-core laptop processor running in the Google Chrome browser:

JavaScriptSpeedOfSortingIntegers

Performance seems to be nearly linear, but is O(nlgn) if the algorithms is in fact Merge Sort. JavaScript was able to sort up to 20 Million integers (32-bit), but Chrome ran out of memory at 100 Million element array size. Performance is nearly 0.8 Million 32-bit integers per second.

C# Sorting

C# provides standard sorting algorithms. The graph below shows performance of C# sort on the Intel i5-6300HQ quad-core laptop processor:

CSharpSpeedOfSortingIntegers

Performance seems to be nearly linear, but could be O(nlgn) if comparison-based sorting algorithm is used. C# was able to sort up to 100 Million integers (32-bit). Performance is nearly 6.3 Million 32-bit integers per second, which is about 8X faster than JavaScript, and is only slightly slower than C++ STL sort.

Python Sorting

Python 2.7.12 (Anaconda 4.1.1 64-bit) and Python 3.6 provide a standard sorting algorithm using Timsort. The graph below shows performance of Python sort on the Intel i5-6300HQ quad-core laptop processor:

PythonSpeedOfSortingIntegers

The blue graph is Python 2.7. The red graph is Python 3.6. Both versions of Python are able to sort up to 100 Million integers in 32-bit range. Performance is about 0.36 Million 32-bit integers per second for Python 2.7, which is nearly 2X slower than JavaScript and 18X slower than C# and nearly 20X slower than C++. Python 3.6 improves performance to about 0.67 Million integers, which is lightly slower than JavaScript, about 8X slower than C#, and over 10X slower than C++.

Putting All Together

The following graph compares performance of standard built-in sorting algorithms of several popular computer languages above. Run-time in seconds is on the vertical axis, with array size of 32-bit integers on the horizontal axis.

MultilanguageSortSpeed

Interactive version of the above graph is at the below link, where individual points are visible, full-screen view is available and individual graphs can be highlighted

Interactive Multi-Language Sorting Performance

C++ STL sort has the highest performance, followed closely by C#, with Python 2.7 being significantly slower (nearly 20X slower than C++). JavaScript is slower than C++ and C# and does not support as large of arrays before running out memory. Python 3.6 is about 2X faster at sorting than Python 2.7. Python 3.6 is about the same performance as JavaScript, but can sort larger arrays. C#, Python and C++ have no trouble with larger capacity.

More Sorting Algorithms

To explore variety of sorting algorithms follow the link below:

Variety of C++ Sorting Algorithms

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