Sorting Problems: Multi-Key Sorts, Custom Comparators, and When Sorting First Solves the Problem

By 0xmote · May 25, 2026 · 17 min read · Updated Sep 27, 2026 Beginner Tutorial

Key takeaways

Most sorting problems are not about implementing a sort. They are about choosing the right order so that the rest of the problem becomes a single linear pass. This guide covers Python's stable sort and key functions, when you really need cmp_to_key, why interval and scheduling greedies sort the way they do, and the comparator and tuple-comparison bugs that quietly produce wrong answers.

Introduction

In interview and contest problems, sorting is rarely the goal. It is the step that turns a messy input into one where the answer can be read off in a single pass: overlapping intervals become adjacent, equal values end up next to each other, and “the best candidate so far” is always the next element. Once the data is sorted, a problem that looked like it needed comparing every pair often needs only a linear scan.

That is also why sorting solutions fail in ways that have nothing to do with sorting algorithms. The code calls sort() correctly and still gets the wrong answer, because it sorted by the wrong key, broke ties in an unintended way, or used a comparator that does not describe a consistent order. This article focuses on those decisions. How quicksort, merge sort and heap sort work internally is covered in Quick Sort, Merge Sort and Heap Sort.

The cost model to keep in mind: a comparison sort costs O(n log n), and it usually dominates the O(n) pass that follows. If a problem has n up to 10^5 or 10^6, “sort, then scan” is almost always fast enough. If you need something faster, the question becomes whether you really need a full order at all (see the last section).

How Python’s Sort Actually Behaves

sort() vs sorted()

list.sort() sorts in place and returns None. sorted() accepts any iterable and returns a new list. The choice matters more than it looks in an interview setting: if a function sorts its argument in place, the caller’s list is modified too, which breaks any later code that relied on the original order or on the original indices.

arr = [5, 2, 8, 1, 9]
result = arr.sort()
print(result)  # None  (a classic bug: x = x.sort())

arr = [5, 2, 8, 1, 9]
sorted_arr = sorted(arr)
print(arr)         # [5, 2, 8, 1, 9]  original untouched
print(sorted_arr)  # [1, 2, 5, 8, 9]

Both use Timsort, which is O(n log n) in the worst case and close to O(n) on input that is already mostly sorted, because it detects existing ascending and descending runs and merges them.

Stability is guaranteed, and it is a tool

Python’s sort is stable: elements that compare equal keep their original relative order. This holds with reverse=True too. Python does not sort ascending and then reverse the list, which would flip the order of ties; equal elements still appear in input order.

records = [("Bob", 90), ("alice", 85), ("Charlie", 85), ("dave", 90)]
print(sorted(records, key=lambda r: r[1], reverse=True))
# [('Bob', 90), ('dave', 90), ('alice', 85), ('Charlie', 85)]

Bob came before dave in the input and still does. Stability is what makes the two-pass technique below correct.

key functions are called once per element

A key function maps each element to a value, and the sort compares those values. Python calls the key exactly once per element and caches the results, so an expensive key (parsing a date, computing a length) costs O(n), not O(n log n). This is one reason key is preferred over a comparator.

Multi-condition sorting with tuples

Tuples compare element by element, so a tuple key expresses “sort by A, then by B” directly. To make a numeric field descending, negate it:

students = [("Alice", 85), ("Bob", 90), ("Charlie", 85), ("David", 90)]
students.sort(key=lambda s: (-s[1], s[0]))  # score desc, name asc
print(students)
# [('Bob', 90), ('David', 90), ('Alice', 85), ('Charlie', 85)]

Negation does not work for strings. A trick you will sometimes see, -ord(name[0]), only looks at the first character and silently mis-orders names that share it. The correct approach for “age ascending, name descending” is two stable passes, secondary key first:

people = [("Alice", 30), ("Bob", 25), ("Charlie", 30), ("Abe", 30)]
people.sort(key=lambda p: p[0], reverse=True)  # secondary: name desc
people.sort(key=lambda p: p[1])                # primary: age asc
print(people)
# [('Bob', 25), ('Charlie', 30), ('Alice', 30), ('Abe', 30)]

The second pass reorders by age, and because it is stable, people with the same age stay in the name-descending order the first pass produced.

Custom Comparators with cmp_to_key

Sometimes the order depends on how two elements relate to each other rather than on a property of each element alone. For those cases functools.cmp_to_key wraps a two-argument comparator that returns a negative number (a goes first), zero (tie), or a positive number (b goes first).

The bool-returning comparator bug

The most common mistake is returning a bool:

from functools import cmp_to_key

bad = sorted([3, 1, 2, 5, 4], key=cmp_to_key(lambda a, b: a > b))
print(bad)   # [3, 1, 2, 5, 4]  not sorted, and no error

good = sorted([3, 1, 2, 5, 4], key=cmp_to_key(lambda a, b: (a > b) - (a < b)))
print(good)  # [1, 2, 3, 4, 5]

cmp_to_key decides “a is less than b” by checking whether the comparator result is < 0. True is 1 and False is 0, so nothing is ever less than anything, every element looks equal to every other, and the stable sort returns the input unchanged. There is no exception, so this only shows up as a wrong answer.

I have made exactly this mistake while switching between languages: in C++ a comparator returns a bool meaning “a goes before b”, and carrying that habit into Python produced a list that was “sorted” into its original order. The fix takes seconds, but only once you know that a silent no-op is the symptom to look for.

Comparators must describe a consistent order

Whatever the language, a comparator must behave like a real ordering: if a < b and b < c then a < c, and no element is less than itself. Python will not crash on an inconsistent comparator, but the result depends on the order the algorithm happened to compare elements in, so the same code can pass small tests and fail hidden ones.

C++ is stricter. std::sort requires a strict weak ordering, and in particular comp(a, a) must be false. A comparator written with <= violates that, and the behavior is undefined:

#include <algorithm>
#include <vector>
#include <cstdio>

int main() {
    std::vector<int> v(100, 7);
    // Wrong: <= is not a strict weak ordering (comp(a, a) is true)
    std::sort(v.begin(), v.end(), [](int a, int b) { return a <= b; });
    std::printf("%d\n", v[0]);
}

When I compiled this with GCC 10 at -O2, it printed 0. A vector containing only 7s came back with a value that was never in it: the unguarded insertion step inside std::sort trusted the comparator to stop it and read past the start of the array. With -D_GLIBCXX_DEBUG the same program aborts with “comparison doesn’t meet irreflexive requirements”. On other inputs the same bug can segfault. Use <, never <=, and build with the debug mode when a sort misbehaves. (Java and C have a related trap: a comparator written as return a - b; overflows for large values of opposite sign and flips the result.)

Classic Problems and Why the Sort Order Works

Problem 1: Largest Number (LeetCode 179)

Arrange non-negative integers so that their concatenation is as large as possible. [3, 30, 34, 5, 9] becomes "9534330".

Sorting the numbers as strings in descending order does not work: "30" sorts before "3", but "330" is larger than "303". The right question is pairwise: should a come before b? Yes if a + b > b + a as strings. That relation is transitive (it is equivalent to comparing the infinite repetitions aaaa... and bbbb...), so it defines a valid order and a comparator is the natural fit.

from functools import cmp_to_key

def largest_number(nums):
    def compare(a, b):
        if a + b > b + a:
            return -1  # a first
        if a + b < b + a:
            return 1   # b first
        return 0

    strs = sorted(map(str, nums), key=cmp_to_key(compare))
    result = "".join(strs)
    return "0" if result[0] == "0" else result

print(largest_number([3, 30, 34, 5, 9]))  # 9534330
print(largest_number([0, 0, 0]))          # 0
print(largest_number([10, 2]))            # 210

The final check matters: [0, 0, 0] would otherwise return "000". It is the edge case this problem is known for.

Problem 2: H-Index (LeetCode 274)

The h-index is the largest h such that at least h papers have at least h citations each. After sorting descending, the paper at index i is the (i+1)-th most cited, so “at least i+1 papers have at least i+1 citations” is exactly citations[i] >= i + 1. Because the list is descending, that condition is true for a prefix and then false forever, so the first failure ends the search.

def h_index(citations):
    c = sorted(citations, reverse=True)  # do not mutate the caller's list
    h = 0
    for i, x in enumerate(c):
        if x >= i + 1:
            h = i + 1
        else:
            break
    return h

print(h_index([3, 0, 6, 1, 5]))   # 3
print(h_index([10, 8, 5, 4, 3]))  # 4
print(h_index([0, 0]))            # 0

This problem also shows when sorting is more than you need. The answer can never exceed n, so citations above n can be clamped to n and counted in buckets, giving O(n):

def h_index_counting(citations):
    n = len(citations)
    buckets = [0] * (n + 1)
    for c in citations:
        buckets[min(c, n)] += 1
    papers = 0
    for h in range(n, -1, -1):
        papers += buckets[h]  # papers with at least h citations
        if papers >= h:
            return h
    return 0

print(h_index_counting([3, 0, 6, 1, 5]))  # 3

Problem 3: Merge Intervals (LeetCode 56)

After sorting by start, an interval can only overlap the intervals that came before it through the most recently merged one. The invariant is: merged holds disjoint intervals in order, and every interval not yet processed starts at or after the start of the last merged interval. So each new interval either overlaps the last merged interval, or it starts after it ends and can never touch anything earlier.

def merge_intervals(intervals):
    if not intervals:
        return []
    intervals = sorted(intervals, key=lambda iv: iv[0])
    merged = [list(intervals[0])]
    for start, end in intervals[1:]:
        last = merged[-1]
        if start <= last[1]:              # overlaps (touching counts)
            last[1] = max(last[1], end)   # max: the new one may be contained
        else:
            merged.append([start, end])
    return merged

print(merge_intervals([[1, 3], [2, 6], [8, 10], [15, 18]]))  # [[1, 6], [8, 10], [15, 18]]
print(merge_intervals([[1, 10], [2, 3], [4, 5]]))            # [[1, 10]]
print(merge_intervals([[1, 4], [4, 5]]))                     # [[1, 5]]

Two details cause most wrong answers. Writing last[1] = end instead of max(last[1], end) breaks on contained intervals like [1, 10], [2, 3]. And whether [1, 4] and [4, 5] overlap is a problem-specific decision: <= merges them, < does not. Read the statement.

Problem 4: Maximum Non-Overlapping Meetings (Activity Selection)

Given meetings as (start, end), choose as many as possible without overlap. The greedy is: sort by end time, then take every meeting that starts after the last one you took ended.

Why end time? Consider any optimal schedule. Its first meeting ends no earlier than the meeting m that ends first overall. Replace it with m: the rest of the schedule still fits, because m frees the room at least as early. Repeating this argument meeting by meeting shows that the greedy choice never loses. Sorting by start time has no such guarantee:

def max_meetings(meetings):
    count = 0
    last_end = float("-inf")  # not 0: starts can be 0 or negative
    for start, end in sorted(meetings, key=lambda m: m[1]):
        if start >= last_end:
            count += 1
            last_end = end
    return count

meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11)]
print(max_meetings(meetings))                   # 3: (1,4), (5,7), (8,11)
print(max_meetings([(0, 10), (1, 2), (3, 4)]))  # 2; sorting by start would give 1

The same algorithm solves LeetCode 435 (minimum intervals to remove is n minus this count) and LeetCode 452 (minimum arrows to burst balloons).

Problem 5: Minimum Meeting Rooms

A different question about the same input: how many rooms are needed so that all meetings happen? Sort by start, and keep a min-heap of end times for rooms in use. If the room that frees up earliest is free by the time the next meeting starts, reuse it; otherwise open a new room.

import heapq

def min_meeting_rooms(meetings):
    rooms = []  # min-heap of end times
    for start, end in sorted(meetings):
        if rooms and rooms[0] <= start:
            heapq.heapreplace(rooms, end)  # reuse the room that frees first
        else:
            heapq.heappush(rooms, end)
    return len(rooms)

print(min_meeting_rooms([(0, 30), (5, 10), (15, 20)]))  # 2
print(min_meeting_rooms([(1, 5), (5, 10)]))             # 1

Here sorting by start is the right choice, because the decision is made when a meeting begins. The contrast with Problem 4 is worth remembering: the sort key follows from the moment the greedy makes its decision.

Sorting as Preparation for Other Techniques

Sort + two pointers, without losing indices

After sorting, if arr[lo] + arr[hi] is too small, no pair using arr[lo] with anything smaller than arr[hi] can work either, so lo can move right. That monotonicity is why two pointers find a target pair in O(n) after the sort. The trap is that sorting destroys the original positions, and problems like Two Sum ask for indices. Sort the indices instead of the values:

def two_sum_indices(nums, target):
    order = sorted(range(len(nums)), key=lambda i: nums[i])
    lo, hi = 0, len(order) - 1
    while lo < hi:
        s = nums[order[lo]] + nums[order[hi]]
        if s == target:
            return sorted([order[lo], order[hi]])
        if s < target:
            lo += 1
        else:
            hi -= 1
    return None

print(two_sum_indices([3, 2, 4], 6))       # [1, 2]
print(two_sum_indices([2, 7, 11, 15], 9))  # [0, 1]

For plain Two Sum a hash map is O(n) and simpler. Sorting pays off when you need all pairs, triples (3Sum), or pairs closest to a target. More on the pattern in Two Pointers.

Sort + binary search

Once sorted, “how many elements are below x” and “how many equal x” become O(log n) queries with bisect:

from bisect import bisect_left, bisect_right

arr = sorted([5, 2, 8, 1, 9, 5])
print(arr)                                         # [1, 2, 5, 5, 8, 9]
print(bisect_left(arr, 6))                         # 4 elements are < 6
print(bisect_right(arr, 5) - bisect_left(arr, 5))  # 2 copies of 5

Sorting once and answering many queries is the win here; for a single query a linear scan is cheaper. The bounds are explained in Binary Search.

Sort + greedy matching

To give cookies to as many children as possible, sort both lists and give each cookie, smallest first, to the least greedy child it can satisfy. A cookie too small for the least greedy remaining child is too small for everyone, so skipping it loses nothing.

def assign_cookies(greed, cookies):
    greed, cookies = sorted(greed), sorted(cookies)
    child = 0
    for c in cookies:
        if child < len(greed) and c >= greed[child]:
            child += 1
    return child

print(assign_cookies([1, 2, 3], [1, 1]))  # 1
print(assign_cookies([1, 2], [1, 2, 3]))  # 2

Where Sorting Solutions Go Wrong

Most failed submissions I have seen on sorting problems, my own included, were not about complexity. They were about the order not being the one the code author thought it was.

Tuple keys that fall through to incomparable values. Sorting (priority, payload) tuples works until two priorities tie, at which point Python compares the payloads. If they are dicts or custom objects, you get TypeError: '<' not supported between instances of 'dict' and 'dict', but only on inputs with ties, so it can pass the samples and fail later. Sort with key=lambda t: t[0], or add a unique tiebreaker such as an index. The same issue appears with heapq when you push (priority, obj).

Numbers stored as strings. sorted(["10", "9", "2", "33"]) gives ['10', '2', '33', '9'], because strings compare character by character. Input read from a file or split from a line is text until you convert it; use key=int or convert first.

Case sensitivity. Uppercase letters sort before lowercase in ASCII, so ["apple", "Banana", "cherry"] sorts to ['Banana', 'apple', 'cherry']. Use key=str.lower (or str.casefold for non-English text) when the problem means alphabetical order.

NaN in float data. Every comparison with nan is false, which breaks the ordering. sorted([3.0, float("nan"), 1.0, 2.0]) returns [3.0, nan, 1.0, 2.0], not sorted at all, and moving the nan to the front changes the result again. Filter NaNs out before sorting.

Mutating the input. Calling .sort() on an argument changes the caller’s data. In a test harness that reuses the input to check your answer, or in a function called twice, that is a bug. Use sorted() unless you own the list.

The debugging habit I rely on is printing the sorted list for a small input that has ties before writing the scan that follows. If the ties come out in the wrong order, no amount of work on the second half of the solution will fix it.

When Not to Sort

Sorting gives you a full order in O(n log n). Many problems need less than that:

Need	Better tool	Cost
Does a pair sum to target?	Hash set/map	O(n)
Top k elements, k much smaller than n	`heapq.nlargest(k, arr)`	O(n log k)
k-th smallest element	Quickselect	O(n) average
Values in a small known range	Counting sort / buckets	O(n + range)
Most frequent elements	`Counter` + heap or buckets	O(n log k) or O(n)

import heapq
print(heapq.nlargest(3, [5, 1, 9, 3, 7, 2]))  # [9, 7, 5]

Sorting remains the right default when you need the elements in order for a later pass, when you need tie-breaking rules, or when n is small enough that the difference does not matter. The alternatives are worth reaching for when the problem statement explicitly asks for better than O(n log n).

Picking the sort key for a problem

Problem shape	Sort by	Then
Merge or count overlaps	Interval start	Linear scan against the last merged interval
Maximum non-overlapping selection	Interval end	Greedy: take if it starts after the last end
Rooms / resources needed	Start	Min-heap of end times
Pairs or triples with a target sum	Value (keep indices if needed)	Two pointers
Many “how many below x” queries	Value	`bisect`
Order defined by pairwise relation	`cmp_to_key` comparator	Join or scan

Python’s sort is stable, including with reverse=True; use tuple keys for multiple conditions and two stable passes for descending strings.
A cmp_to_key comparator returns negative, zero, or positive, never a bool.
In C++, a comparator must be a strict weak ordering: <, never <=.
Choose the sort key by asking at which moment your greedy makes its decision.