Sorting and Comparators

1. Sorting is often preprocessing, not the final answer

An unsorted collection has too many possible relationships. Sorting pays O(n log n) once to create an invariant: everything left is no greater, everything right is no smaller. That invariant unlocks:

• adjacent duplicate detection,
• two pointers for pairs and triples,
• binary search,
• interval merging,
• greedy earliest/latest choices,
• grouped equal values.

The interview sentence is: “I will spend O(n log n) to make X possible in one linear pass.”

2. Language APIs

sort(nums.begin(), nums.end());
sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
    if (a.end != b.end) return a.end < b.end;
    return a.start < b.start;
});

nums.sort((a, b) => a - b);
items.sort((a, b) => a.end - b.end || a.start - b.start);

JavaScript’s default is lexicographic: [10, 2].sort() becomes [10, 2], not [2, 10]. Always write the numeric comparator explicitly.

3. Comparator contracts

For ascending C++ order, comp(a,b) means a belongs before b. It must be false when a and b are equal. Writing a.value <= b.value is invalid because both comp(a,b) and comp(b,a) can be true.

For JavaScript:

• negative → a before b,
• zero → tied,
• positive → b before a.

Use a secondary key to make ties intentional rather than accidental.

4. Stable sort and original order

A stable sort keeps equal-key items in their original relative order. C++ sort is not stable; stable_sort is. Modern JavaScript Array.prototype.sort is specified as stable, but writing an explicit secondary key still makes intent clearer.

More important: sorting may destroy information you need. Two Sum must return original indices, so a hash map is cleaner. If sorting objects, carry their original index:

const indexed = nums.map((value, index) => ({ value, index }));
indexed.sort((a, b) => a.value - b.value);

5. Three examples

• 3Sum: sorting lets one fixed value use two pointers and skip adjacent duplicates.
• Car Fleet: sorting by position makes the fleet directly ahead known.
• Group Anagrams: sorting each word creates a canonical key, though frequency signatures can be faster.

6. What you need to know about sorting algorithms

For interviews, understand the tradeoffs rather than reimplementing every sort:

7. Traps

1. Forgetting the JavaScript numeric comparator.
2. Returning <= from a C++ comparator.
3. Subtracting enormous integers in a JS comparator when precision is already unsafe.
4. Claiming sorting is O(1) space without qualifying the implementation and recursion stack.
5. Sorting automatically when O(n) hashing is required by the constraints.

8. Learning gate

Write comparators for: ascending numbers, intervals by end then start, and people by descending score then ascending name. State whether original order and stability matter in each case.