Implementing Stable Multi-Key Sorting in TypeScript

Introduction

Welcome to the first lesson in our module on Sorting and Binary Search. Sorting data is a fundamental operation in computer science, not just for presenting information in a human-readable order, but as a powerful prerequisite for many advanced algorithms. Often, a complex search or processing problem can be simplified dramatically by first sorting the input.

In this lesson, we will focus on mastering TypeScript's built-in sort method to handle common scenarios you'll encounter in algorithmic problems. We will cover how to write custom comparator functions to correctly sort numbers, how to implement multi-key sorting for complex objects or tuples, and the important concept of sort stability. Given your extensive front-end development experience, you are likely familiar with Array.prototype.sort(), so we will build on that foundation to establish a robust and principled approach for its use in algorithm design.

The sort() Comparator

As you know, Array.prototype.sort() is a powerful tool, but it has a quirk that can easily lead to bugs if you're not careful: by default, it sorts elements lexicographically (as strings).

const numbers = [10, 2, 1, 100];
numbers.sort();
console.log(numbers); // Output: [1, 10, 100, 2]

This is clearly not the numerical order we want. To sort elements based on a custom logic, we must provide a comparator function. This function takes two arguments, a and b, and must return a number that dictates their relative order.

To understand the contract of this comparator, let's watch a brief and clear explanation.

To summarize the key rules:

• Return a negative value (< 0): a should come before b.
• Return a positive value (> 0): b should come before a.
• Return zero (0): a and b are considered equal for sorting purposes; their relative order might not change (we'll discuss this more under "stability").

For sorting numbers in ascending order, this leads to a very common and concise pattern: (a, b) => a - b.

• If a < b, a - b is negative, so a comes first.
• If a > b, a - b is positive, so b comes first.
• If a === b, a - b is zero.

For descending order, you simply reverse the subtraction: (a, b) => b - a.

Sorting by Multiple Criteria

In many problems, you'll need to sort by a primary criterion, and then use a secondary criterion to break ties. For instance: "sort players by score descending, then by name ascending."

The standard way to implement this is with a single comparator function that chains these comparisons. The logic is:

1. Compare a and b on the primary key.
2. If the primary keys are not equal, you've found the correct order. Return the result of the comparison.
3. If the primary keys are equal, return the result of comparing them on the secondary key.
4. This pattern can be extended to tertiary keys and beyond.

The following video demonstrates this "fall back" logic clearly.

This leads to an elegant and highly readable pattern in TypeScript/JavaScript, often using the logical OR (||) operator for short-circuiting:

// Primary: score descending. Secondary: name ascending.
players.sort((a, b) => {
  // Primary comparison
  const scoreDifference = b.score - a.score;
  if (scoreDifference !== 0) {
    return scoreDifference;
  }

  // Secondary comparison (if scores are tied)
  return a.name.localeCompare(b.name);
});

// A more concise version using short-circuiting:
players.sort((a, b) => (b.score - a.score) || a.name.localeCompare(b.name));

The expression (b.score - a.score) evaluates to a non-zero number if the scores are different, and the || operator returns this first "truthy" (non-zero) value. Only if b.score - a.score is 0 ("falsy") does the expression proceed to evaluate and return the result of the localeCompare.

Let's look at a complete example from a typical LeetCode problem.

Understanding Sort Stability

The concept of a stable sort is an important property of sorting algorithms. A sorting algorithm is stable if it preserves the original relative order of elements that have equal sort keys.

Why does this matter?

1. Predictability: It makes the behavior of your code easier to reason about.
2. Simplified Multi-key Sorting: With a stable sort, you can sort by multiple criteria by performing multiple sorts in reverse order of key priority. To sort by score (primary) then name (secondary), you could:
   1. Sort by name.
   2. Then, sort by score.
      Because the second sort is stable, any players with the same score will remain in their name-sorted order.

Fortunately, you can rely on this behavior in modern environments.

As the text confirms, since the ES2019 specification, Array.prototype.sort() is guaranteed to be stable. While the multi-sort trick is good to know, the single chained comparator we saw earlier is generally more efficient and explicit.

A Practical Example: Sorting Dictionary Values

A common task is to sort the entries of an object or Map by their values. Since objects don't have an inherent order, the process involves converting the object into an array, sorting it, and optionally converting it back.

The steps are as follows:

1. Object.keys(cityPopulation) gets an array of the keys (['Chicago', 'NewYork', 'LosAngeles']).
2. .map(city => [city, cityPopulation[city]]) transforms this array of keys into an array of [key, value] tuples.
3. .sort((a, b) => a[1] - b[1]) sorts this array of tuples based on the second element of each tuple (the population), which is a[1] and b[1].
4. Finally, forEach is used to build a new object from the sorted tuples.

Conclusion

In this lesson, we formalized the use of TypeScript's Array.prototype.sort for algorithmic problem-solving. We've established a solid foundation for one of the most common prerequisite steps in algorithms.

Here are the key takeaways:

• Always provide a custom comparator function when sorting anything other than strings. For numbers, use (a, b) => a - b for ascending order and (a, b) => b - a for descending.
• The comparator's return value (<0, 0, >0) dictates the final ordering of elements a and b.
• For multi-key sorting, use a single comparator that checks the primary key first, and only proceeds to the secondary key if the primary keys are tied. The logical OR (||) operator provides a concise way to chain these checks.
• Modern JavaScript engines provide a stable sort, meaning elements with equal keys retain their original relative order.

In our next lesson, we will explore the first of many applications of this skill, answering the question: "When can sorting replace a more complicated search with a structured scan?" You'll see how sorting unlocks powerful and efficient patterns for solving a wide range of problems.