Sorting Tricks

Custom Comparator

Sort by a problem-specific rule. Example: to form the largest number from an array, sort with comparator: a+b vs b+a (string concatenation). '9' before '34' because '934' > '349'. Think about what ordering you need.

O(n log n)

O(n)

How It Works

A custom comparator redefines what 'less than' means so that a standard sort produces a problem-specific order. The classic example is Largest Number: to decide whether digit-string a precedes b, compare the concatenations a+b and b+a and put the pair whose concatenation is larger first — '9' precedes '34' because '934' beats '349'. Sorting with that rule and concatenating yields the maximum number.

The sort itself remains O(n log n) comparisons, though each comparison may cost more than O(1) (string concatenation makes Largest Number O(n log n * L)). Correctness rests on the comparator being a valid total order — transitive, antisymmetric, consistent — otherwise library sorts can produce arbitrary output or crash. Comparator design also underlies multi-key sorts (sort by frequency, break ties alphabetically) and interval orderings, making it one of the most reused micro-skills in interview problems.

Step-by-Step Visualization

Form largest number from [3, 30, 34, 5, 9]

Compare3 vs 30: '330' > '303'

1/3

Code

Java

static String largestNumber(int[] nums) {
  String[] strs = new String[nums.length];
  for (int i = 0; i < nums.length; i++) strs[i] = String.valueOf(nums[i]);

  Arrays.sort(strs, (a, b) -> (b + a).compareTo(a + b));

  if (strs[0].equals("0")) return "0";
  StringBuilder sb = new StringBuilder();
  for (String s : strs) sb.append(s);
  return sb.toString();
}

// Example: largestNumber(new int[]{10, 2}) → "210"
// Because "210" > "102"

Tips & Gotchas

1Define a custom comparator that captures the problem's ordering

2For largest number: compare a+b vs b+a as strings

3Always handle edge cases like leading zeros

Practice Problems

1Largest Number
2Sort the People
3Custom Sort String
4Reorder Data in Log Files

About the Sorting Tricks Pattern

Patterns where sorting is used as a tool to solve a different problem.

Key insight

Sorting unlocks binary search, two-pointer, and greedy. Always ask: can I sort first? Custom comparators solve tricky ordering problems. Know QuickSelect for O(n) expected Kth element.

Common Sorting Interview Problems

Sort Colors
Kth Largest Element
Merge Intervals
Largest Number
Sort List
Meeting Rooms

Frequently Asked Questions

Why does comparing a+b against b+a give the largest number?

The comparison directly encodes the objective: it asks which local ordering of the pair produces the larger concatenation. Since the relation is a total order (transitivity can be proven from properties of concatenation), sorting by it is a greedy that is globally optimal — any adjacent out-of-order pair could be swapped to improve the result.

What goes wrong if my comparator violates transitivity?

Sorting algorithms assume a strict weak ordering; violating it yields undefined behavior — Java throws 'Comparison method violates its general contract', C++ can segfault, and results become input-order dependent. Always verify that compare(a,b) and compare(b,c) implying compare(a,c) actually holds for your rule.

How do I sort by multiple keys, like frequency then alphabetical order?

Chain the criteria inside one comparator: compare by the primary key and fall back to the secondary key only on ties. Alternatively, exploit stability — sort by the secondary key first, then stably sort by the primary key — which composes any number of levels.