Sorting Arrays of Objects in JavaScript with Radix Sort

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 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 methods 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 shortly. For now, I’ll just say that Radix Sort is faster than the built-in JavaScript sort, by 30-50%, which is not as dramatic of a speedup as 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 these can be duplicates, 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.

Surprisingly, it’s only a tiny modification to the LSD Radix Sort implementation to support sorting arrays of objects. The modification is the addition of getKey function. The rest of the code is the same as was used for sorting arrays of unsigned integers.

GitHub repository of all the code with usage examples

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

Advertisements

2 thoughts on “Sorting Arrays of Objects in JavaScript with Radix Sort

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