Where it runs
1. The problem
Binary search works only on sorted data. Sorting is how the data gets that way. And once data is in order, a whole set of new problems becomes solvable: merging overlapping ranges, building a schedule, finding the busiest moment.
You have a game leaderboard. The highest score should be on top. If two players have the same score, the one who finished faster (with the smaller time) goes higher. If the time is the same too, the name decides, A to Z. So the order depends on three things at once, and each has its own priority.
JavaScript can sort an array, but without help it knows only one rule, and it is a surprising one. [2, 10, 1].sort() gives [1, 10, 2]. The sort turned the numbers into text and compared the text. The character "1" comes before the character "2", so "10" ended up before "2".
Any order other than text order you have to set yourself. You write the rule as a small function. It is called a comparator (from "compare").
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is included[{ priority: 2, name: "cat" }, { priority: 1, name: "eve" }, { priority: 2, name: "ann" }, { priority: 3, name: "bob" }, { priority: 1, name: "dan" }].sort(cmp)| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| priority | 2 | 1 | 2 | 3 | 1 |
| name | cat | eve | ann | bob | dan |
Sort by priority, and by name only when priorities tie. An insertion sort calls the comparator so every call can be seen.
Recognise it
Say these words and it is this pattern
- 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
Looks similar, isn't
- 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.
n up to 1e6 gives O(n log n) comparisons. A slow comparator multiplies that, so precompute the key.
On LeetCode
Problems where the order is a rule you write, such as by frequency and then value, by another string's order, by distance, or by which joined string reads larger. One comparator returns a negative number, a positive number or zero.
Two keys checked in order, frequency going up, then value going down.
The comparator subtracts the two letters' positions in order.
Compare squared distances, x * x + y * y, and take the first k.
Put a before b when the string a + b reads larger than b + a.