Sort with a custom comparator

How does Sort with a custom comparator work?

A comparator takes two items and returns a number. Negative means the first one comes earlier.

Zero means the two are tied. A stable sort then leaves them in their original order.

For plain numbers, return a minus b to go ascending. Avoid the subtraction when values can overflow.

For several keys, compare the first one. Fall through to the next key only on a tie.

The rule has to be consistent. If a beats b and b beats c, then a beats c.

The comparator runs n log n times. Anything expensive inside it should be computed once beforehand.

1. [Ann 30, Bo 25, Cy 30]Sort by age first, then by name.
2. compare(Ann, Bo)30 against 25 returns positive. Bo belongs earlier.
3. compare(Ann, Cy)The ages tie at 30. The rule falls through to the name.
4. Ann before CyThe second key decides it. Ann wins on the name.
5. [Bo 25, Ann 30, Cy 30]Two keys, one pass. The order is now total.

// sort by a custom / multi-key order
items.sort((a, b) => {
    if (a.priority !== b.priority) return a.priority - b.priority;
    return a.name.localeCompare(b.name);
});

A worked example of Sort with a custom comparator

Arrange numbers into the largest one

You get a list of non-negative integers. Arrange them so the joined digits read as the largest number.

Return a string, because the result can be huge.

Sorting by value is wrong here, since 9 must come before 30.

Compare two numbers by the two strings they can form. Put a first when a plus b reads larger.

function largestNumber(nums) {
    const parts = nums.map(String);

    // whichever joined order reads larger wins the comparison
    parts.sort((a, b) => (b + a).localeCompare(a + b));

    if (parts[0] === "0") return "0"; // every value was zero
    return parts.join("");
}

When should you use Sort with a custom comparator?

These phrases in a problem statement point here:

• •sort by multiple fields / tie-break on a second key
• •custom order (not plain ascending)
• •sort descending, or by a computed key
• •"sort so that X comes before Y when..."
• •reorder objects/records, not raw numbers

What is Sort with a custom comparator confused with?

• Fast sort (merge / quick): That page is about how the sorting happens. This one is about the order you ask for.
• Greedy (exchange argument): A greedy proof usually decides which order is correct. The comparator is how you write it down.
• Intervals: merge & insert: Interval work starts with a sort by start time. The merging is a separate step after it.
• Binary heap / priority queue: A heap takes the same comparator but keeps only the front. Use it when data is still arriving.

Common mistakes with Sort with a custom comparator

• Sorting numbers with no comparator

  JavaScript compares as strings by default, so 10 lands before 9. Always pass a comparator.

• Subtracting very large values

  The difference can overflow or lose precision. Return minus one, zero or one instead.

• Writing a rule that contradicts itself

  An inconsistent comparator gives an undefined result. Some engines throw instead of sorting.

• Computing an expensive key inside it

  The comparator runs on every comparison, not once per item. Build the key first, then sort by it.

Which interview problems use Sort with a custom comparator?

• Largest number: Order by which of the two joined strings reads larger.
• Merge intervals: Sort by start time before anything else happens.
• Meeting rooms: The same sort, then a check on each neighbouring pair.
• Sort by increasing frequency: Frequency is the first key, the value is the second.
• Custom sort string: The order comes from another string entirely.
• Relative sort array: Listed values first, everything else ascending.
• K closest points to origin: Sort by the squared distance, never the square root.

What is the time and space complexity of Sort with a custom comparator?

O(n log n)

n up to 1e6 gives O(n log n) comparisons. A slow comparator multiplies that, so precompute the key.