Faster Sorting in JavaScript

JavaScript is taking over the world as the language of the web. When it comes to sorting, JavaScript is about 9 times slower than C++ and C#, but is slightly faster than Python 3.6, as I’ve shown in the previous post Sorting Speed of Several Languages. In this post, let’s explore the possibility of sorting faster in JavaScript.

By default, JavaScript sorts arrays of strings. If you try to sort an array of integers, the result will be sorted wrong. JavaScript’s built-in sorting algorithm is nicely general purpose. It uses a comparison function provided by the user to sort any data type that can be compared. For sorting an array of integers correctly, a common approach is to provide a comparison function that works properly for integers instead of using the default comparison for strings. One such comparison function is provided on How to sort an array of integers correctly StackOverflow topic. This leads to a correct sorting algorithm for arrays of integers.

Using comparisons for sorting puts a well known performance bound on the algorithm of O(nlogn). It may be possible to increase performance by using a sorting algorithm that does not use comparisons, such as the Radix Sort. I’ve implemented the least-significant-digit (LSD) version of the Radix Sort in JavaScript, and verified it’s correctness by comparing results to JavaScript built-in sort. Below is a graph comparing performance of LSD Radix Sort for arrays of random unsigned integers:

JavaScriptSortComparison

X-axis is the size of array, and Y-axis is time in seconds to sort that array. Smaller values on the Y-axis mean the algorithm took less time to sort. LSD Radix sort is much faster for sorting, compared to JavaScript built-in sort. I used the same array size filled with the same random unsigned integer values for both sorting algorithms. Above 20 million element array size, performance becomes much more variable for JavaScript sort, and Radix Sort slows down as well. This is most likely due to memory allocation cutting into performance for both algorithms.

The graph below shows how much faster LSD Radix Sort is:

JavaScriptSortToLSDRadixSort

LSD Radix Sort is 5 to 50 times faster than JavaScript built-in sort for all array sizes tested. Above 50 million elements the Chrome browser (64-bit) ran out of memory. Chrome was the only browser I have tested so far.

LSD Radix Sort Implementation

var extractDigit = function( a, bitMask, shiftRightAmount ) {
    var digit = (a & bitMask) >>> shiftRightAmount; // extract the digit we are sorting based on
    return digit;
}
// June 2017 Victor J. Duvanenko High Performance LSD Radix Sort for arrays of unsigned integers
function radixSortLSD(_input_array) {
    var numberOfBins = 256;
    var Log2ofPowerOfTwoRadix = 8;
    var _output_array = new Array(_input_array.length);
    var count = new Array(numberOfBins);
    var _output_array_has_result = false;

    var bitMask = 255;
    var shiftRightAmount = 0;

    var startOfBin = new Array( numberOfBins );
    var endOfBin   = new Array( numberOfBins );

    while( bitMask != 0 ) // end processing digits when all the mask bits have been processed and shifted out, leaving no bits set in the bitMask
    {
        for (var i = 0; i < numberOfBins; i++ )
            count[ i ] = 0;
        for (var _current = 0; _current < _input_array.length; _current++ ) // Scan the array and count the number of times each digit value appears - i.e. size of each bin
            count[ extractDigit( _input_array[ _current ], bitMask, shiftRightAmount ) ]++;
 
        startOfBin[ 0 ] = endOfBin[ 0 ] = 0;
        for( var i = 1; i < numberOfBins; i++ )
            startOfBin[ i ] = endOfBin[ i ] = startOfBin[ i - 1 ] + count[ i - 1 ];
        for ( var _current = 0; _current < _input_array.length; _current++ )
            _output_array[ endOfBin[ extractDigit( _input_array[ _current ], bitMask, shiftRightAmount ) ]++ ] = _input_array[ _current ];
 
        bitMask <<= Log2ofPowerOfTwoRadix;
        shiftRightAmount += Log2ofPowerOfTwoRadix;
        _output_array_has_result = !_output_array_has_result;
 
        var tmp = _input_array, _input_array = _output_array, _output_array = tmp; // swap input and output arrays
    }
    if ( _output_array_has_result )
        for ( var _current = 0; _current < _input_array.length; _current++ ) // copy from output array into the input array
            _input_array[ _current ] = _output_array[ _current ];
 
    return _input_array;
}

 

Notice in the implementation all memory allocations are performed before the main while loop. This is most likely the reason the Radix Sort LSD implementation suffers less performance loss than the JavaScript sort as array size grows above 20 million elements and memory allocation influences performance. Radix Sort LSD continues to perform well for arrays up to 33 million elements, and then starts slowing down as well.

Usage Example

function simpleUsageExampleOfRadixSortLSD() {
    var arrayToBeSorted = [ 99, 1999999999, 51, 23, 102];
    var sortedArray = radixSortLSD(arrayToBeSorted);
    for ( var _current = 0; _current < sortedArray.length; _current++ ) {
        console.log(sortedArray[_current]);
    }
}

Performance for Presorted Array

The graph below shows performance of JavaScript built-in sort versus LSD Radix Sort for presorted arrays:

JavaScriptSortVsRadixSortPresorted

LSD Radix Sort is consistently and substantially faster than JavaScript’s built-in sort, especially for presorted arrays smaller than 30 Million integers. LSD Radix Sort is 5 to 34 times faster for arrays up to 50 Million elements. For arrays smaller than 30 Million integers, LSD Radix Sort is 16 to 34 times faster.

Constant Array

The graph below shows performance of JavaScript built-in sort versus LSD Radix Sort for arrays smaller than 20 Million integer arrays filled with a constant value, such as all values of 255:

JavaScriptVsLsdRadixSortConstant

LSD Radix Sort shows more consistent performance than JavaScript sort for constant value filled arrays under 20 Million elements. For arrays larger than 20 Million performance becomes more erratic for both algorithms, most likely due to memory allocation performance variations.

Conclusion

It’s hard to see from the graphs that the LSD Radix Sort runs between 24 and 42 MegaIntegers per second, when sorting arrays smaller than 30 MegaIntegers. This level of performance beats built-in algorithms of all languages that were measured in Sorting Speed of Several Languages (C++, C#, and Python). It is also within 2X of LSD Radix Sort implementation in C++, which was the starting point for the above JavaScript code.

GitHub repository of all the code with usage examples

Extra

LSD Radix Sort is also a stable sort as is described in Stable Sorting in JavaScript

 

Advertisements

One thought on “Faster Sorting in JavaScript

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