Faster Sorting in JavaScript

JavaScript is taking over the world as the language of the web. When in 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. 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

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

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

Performance measurements coming – faster than JavaScript built-in sort.

Constant Array

Performance measurements coming – slower than JavaScript built-in sort.

 

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