Faster Sorting Object Arrays in JavaScript

So far we’ve been sorting arrays of unsigned integers in JavaScript. This is very useful at times. Sorting objects based on an embedded unsigned integer field is useful in many more cases. For instance, you have an array of objects, each holding a persons name and an id. Sorting this array by id’s using JavaScript’s built-in sorting is done as follows:

function compareIDs(a, b) { return a.id - b.id; }

function javaScriptSortingObjectsExample()
{
   const people = [
      { person: 'George', id: 2},
      { person: 'Alexa',  id: 4},
      { person: 'David',  id: 1}
   ];
   console.log(people.sort(compareIDs));
}

Note the use of a custom comparison function (compareIDs), which is used to compare numeric field (id) being sorted by. Sorting using LSD Radix Sort is shown below:

function getKey(elementA) { return elementA.id; }

function javaScriptSortingObjectsExample()
{
   const people = [
      { person: 'George', id: 2},
      { person: 'Alexa',  id: 4},
      { person: 'David',  id: 1}
   ];
   console.log(radixSortLSD(people, getKey));
}

Note the simple custom function (getKey), which provides access to the numeric value being sorted by.

Both methods produce the same results, for this example. Note how similar the two functions are. The built-in JavaScript sort requires a custom comparison function (compareIDs) to sort integers correctly. The Radix Sort requires a simple custom function (getKey) to access the numeric element within the object being sorted by.

Performance

I’ll provide performance comparison graphs shortly. For now, I’ll just say that Radix Sort is faster than the built-in JavaScript sort, by about 15X, which is nearly as dramatic of a speedup as we experienced for sorting purely unsigned integer arrays.

Because each object holds more data than just numbers, the Chrome browser runs out of memory at smaller array size – around 10 million elements.

Stability

One advantage that LSD Radix Sort provides is stability. If you have numerical values being sorted by, such as id’s above, and duplicates are allowed, then most likely you’ll care about stability. For further discussion on stability see my blog entry Stable Sorting in JavaScript

Source Code

I put together hpc-algorithms npm, which is open source and free, containing the implementation of this algorithm. The source code is in the GitHub/hpc-algorithms repository.

Several new recent (2019) improvements have been made to dramatically raise performance. In fact, this algorithm in JavaScript outperforms the same algorithm in C#.

GitHub repository of all the code with usage examples

Enjoy, and let me know if it’s been helpful.

Advertisements

2 thoughts on “Faster Sorting Object Arrays 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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s