Sorting in TypeScript: sort() and Compare Functions

In JavaScript, we can sort the elements of an array easily with a built-in method called the sort() function.

The default sort order is ascending, built upon converting the elements into strings, then comparing them lexicographically.

Array of strings:

When we use the sort() method, elements will be sorted in ascending order (A to Z) by default:

let teams = ['Real Madrid', 'Manchester Utd', 'Bayern Munich', 'Juventus'];

teams.sort(); 

// ['Bayern Munich', 'Juventus', 'Manchester Utd', 'Real Madrid']

Arrays of numbers:

Sorting numbers is unfortunately not that simple. If we apply the sort() method directly to a numbers array, we will see an unexpected result:

let numbers = [3, 23, 12];

numbers.sort(); // --> 12, 23, 3

By default, the sort() function sorts values as strings.

This works well for strings ("Apple" comes before "Banana").

However, if numbers are sorted as strings, "3" is bigger than "23", because "3" is bigger than "2".

Because of this, the sort() method will produce incorrect results when sorting numbers.

Solution: The Compare Function

Luckily, we can support the sort() method with a basic comparison function which will do the trick:

function(a, b) {return a - b}

When the sort() function compares two values, it sends the values to the compare function, and sorts the values according to the returned (negative, zero, positive) value:

• If the result is negative a is sorted before b.
• If the result is positive b is sorted before a.
• If the result is 0 no changes are done with the sort order of the two values.

All we need to is using the compare function inside the sort() method:

let numbers = [3, 23, 12];

numbers.sort(function(a, b) {return a - b}); // --> 3, 12, 23

JavaScript gives us a way to make this code shorter using arrow functions:

numbers.sort(function(a, b) {return a - b});

// can be rewritten as:
numbers.sort((a, b) => {return a - b});

// and even as:
numbers.sort((a, b) => a - b);

If we want to sort the numbers in descending order, this time we need to subtract the second parameter (b) from the first one (a):

let numbers = [3, 23, 12];

numbers.sort((a, b) => b - a); // --> 23, 12, 3

Arrays of pairs:

Let's see another scenario when the comparison function is very useful: sorting an array, where each element is another array consisting of two numbers, ascending by the second values and in case of equality, descending by the first values:

let pairs = [[1, 3], [10, 1], [12, 1], [7, 5]];

//sort the array

// Desired outcome: pairs = [[12, 1], [10, 1], [1, 3], [7, 5]]

Here is how we would do that:

let pairs = [[1, 3], [10, 1], [12, 1], [7, 5]];

pairs.sort((a, b) => {
    if(a[1] == b[1]) {
        return b[0] - a[0];
    }
    return a[1] - b[1];
});

// pairs = [[12, 1], [10, 1], [1, 3], [7, 5]]

Time Complexity:

Sorting an array via sort() takes O(n * log n * C) time, where C is the time taken to compare two elements from the array.

It takes O(1) (constant time) to compare two numbers, therefore sorting an array of numbers takes O(n log n).

However, it takes O(L) to compare two strings, therefore sorting an array of strings takes O(n * log n * L), where L is the average length of the strings.

Space Complexity:

The sort() method sorts the elements of an array in place (transforms the array directly, using no auxiliary data structure), so the extra space used for this is O(1).

Assignment
Follow the Coding Tutorial and let's sort some arrays.

Hint
Look at the examples above if you get stuck.