Random Picture

photo by Liana S on Unsplash


Sorting Arrays

The .sort() method sorts the elements of an array in place and returns the sorted array. By default, the sort method converts elements to strings and sorts them in lexicographical order.

Let me write some examples that will reinforce this concept in my brain.

Here, I take the following example with strings as elements:

const owners = ["Charles", "Ernie", "Kenny", "Shaq", "Draymond"];
console.log(owners.sort()); // ['Charles', 'Draymond', 'Ernie', 'Kenny', 'Shaq']
 
// now if we check the owners array again:
console.log(owners); // ['Charles', 'Draymond', 'Ernie', 'Kenny', 'Shaq'] (the array elements got sorted lexicographically)

How about numbers as elements? Let’s look at the following example:

const movements = [200, 450, -400, 3000, -650, -130, 70, 1300];
console.log(movements.sort()); // [-130, -400, -650, 1300, 200, 3000, 450, 70] (weird...)

This is because, as mentioned in the first paragraph above, the .sort() method converts elements to strings and sorts them in lexicographical order. This means that numbers, too, get converted to strings. In that sense, the sorting makes sense. But we don’t want that, do we?

So how do we fix this?

To sort numbers or other types more effectively, we need to provide a comparator function.

Comparator Function?
Keeping it relevant to the topic here, the comparator function takes two arguments, typically referred to as a and b. This function should return:

  • A negative number if a should come before b.
  • A positive number if a should come after b.
  • Zero if a and b are considered equal.

I’ll take the same example as above for this and apply the comparator function.

const movements = [200, 450, -400, 3000, -650, -130, 70, 1300];
 
// ascending order
movements.sort((a, b) => {
  if (a > b) return 1;
  if (a < b) return -1;
  return 0;
});
 
console.log(movements) // [-130, -400, -650, 1300, 200, 3000, 450, 70]

That was the ascending order. But what is happening? Two things:

Comparison Logic

  • If a > b, the comparator function returns 1, indicating that a should come after b.
  • If a < b, the comparator function returns -1, indicating that a should come before b.
  • If a and b are equal, the comparator function returns 0, indicating no change in order.

But why does the positive return value swap a and b?

  • The sort method uses the return value of the comparator function to determine the relative order of a and b.
  • When the function returns a positive value (1), it indicates that a is greater than b, so a should come after b in the sorted order.
  • When the function returns a negative value (-1), it indicates that a is less than b, so a should come before b in the sorted order.
  • Returning 0 means their order doesn’t need to change because they are considered equal in the sort order.

Note that the original movements array has been changed here. The .sort method can change an array from its original state.

Another important note here is that it doesn’t really matter whether it’s 1 or a different positive number, as long as it's more than 0, it will always work.
Same is true for -1. As long as it's a negative number, it will always work.

Then, let’s use this logic to simplify our comparison logic.

const movements = [200, 450, -400, 3000, -650, -130, 70, 1300];
 
// ascending order
movements.sort((a, b) => a - b);
 
console.log(movements) // [-130, -400, -650, 1300, 200, 3000, 450, 70]

So, what’s going on in here? How I understand it is that the sort order here for any 2 consecutive elements in the array is (a, b) (and not the default lexicographical order since the order here is explicitly stated). If a - b is positive, it means a is bigger than b. This causes .sort to switch the positions of a and b.

In a broad overview, the result of a - b provides the necessary comparison:

  • If a > b, then a - b is positive, so a should come after b.
  • If a < b, then a - b is negative, so a should come before b.
  • If a === b, then a - b is 0, indicating they are equal in the sort order.

Visualizing the Sorting Process

  • First Pass: Compare 200 and 450

    • 200 - 450 = -250 (200 stays before 450)
  • Next Pass: Compare 200 and -400

    • 200 - (-400) = 600 (200 moves after -400)
  • Next Pass: Compare -400 and 450

  • -400 - 450 = -850 (-400 stays before 450)

  • Continue: The process continues for all elements in a similar manner until the entire array is sorted.


Conversely, we can do a denominator-order sorting with the same logic:

const movements = [200, 450, -400, 3000, -650, -130, 70, 1300];
movements.sort((a, b) => b - a);
 
console.log(movements); // [3000, 1300, 450, 200, 70, -130, -400, -650]

Caveat

If there is a mixed array, sort method is not advised.


This sorting in computer programming is called the comparison-based sorting.