Sorting in Practice: Built-in Sorts and Custom Comparators

In real interviews you call the built-in sort far more often than you implement one. What matters is knowing what the library guarantees (time bound, stability), expressing the order you need with a key or comparator that is actually correct, and recognizing the many problems that become simple once the data is sorted.

Intuition

What the standard libraries use:

Language / call	Algorithm	Stable	Worst case
Python sorted, list.sort	Timsort (run-detecting merge sort; recent CPython versions refine the merge policy)	Yes	O(n log n), O(n) on already sorted runs
Java Arrays.sort on objects, Collections.sort	Timsort	Yes	O(n log n)
Java Arrays.sort on primitives	Dual-pivot quicksort	No (irrelevant for primitives)	O(n log n) in modern JDKs
C++ std::sort	Introsort: quicksort, heap sort fallback, insertion sort for small ranges	No	O(n log n) since C++11
C++ std::stable_sort	Merge sort	Yes	O(n log n) with a buffer, O(n log^2 n) without
C++ std::partial_sort	Heap of the first k	No	O(n log k)
C++ std::nth_element	Quickselect variant (introselect)	No	O(n) on average

Timsort scans for already ordered stretches ("runs"), reverses descending ones, extends short runs with binary insertion sort, and merges runs with a stack-based policy that keeps merges balanced. That is why sorting nearly sorted data in Python is close to linear.

Keys versus comparators:

• A key function maps each element to a value that Python compares natively (numbers, strings, tuples). It is called once per element, and tuples give lexicographic multi-level ordering for free.
• A comparator decides the order of two elements. Use it only when the order cannot be expressed as a key, typically because it depends on both elements together. In Python, wrap it with functools.cmp_to_key; it must return a negative number, zero or a positive number, not a boolean.
• In C++ a comparator returns true when the first argument must come first and has to be a strict weak ordering: cmp(a, a) is false, it is transitive, and "neither comes first" behaves like equality. Using <= violates this and can make std::sort read out of bounds.

When to use it in interviews / OAs

Sorting is the first thing to try when a problem involves:

• Duplicates or closest pairs: after sorting, equal or nearest values are adjacent, so one linear scan finds them.
• Searching: binary search and two pointers both need sorted input.
• Intervals and sweeps: sort intervals by start (merging) or by end (scheduling); sort events by time to sweep.
• Greedy orderings: assign the largest to the largest, process tasks by deadline, form the largest number.
• Canonical forms: the sorted letters of a word identify its anagram group.
• Ranking: replace values by their rank (coordinate compression).

Template

Multi-level keys

Sort by increasing frequency and break ties by decreasing value. Negating a number reverses its order inside a tuple key:

from collections import Counter


def sort_by_frequency(nums: list[int]) -> list[int]:
    freq = Counter(nums)
    return sorted(nums, key=lambda x: (freq[x], -x))

Strings cannot be negated. To sort by age descending and then name descending, rely on stability and sort twice, secondary key first. reverse=True keeps equal elements in their original order, so stability survives:

def sort_people(people: list[tuple[str, int]]) -> list[tuple[str, int]]:
    out = sorted(people, key=lambda p: p[0], reverse=True)  # secondary: name, descending
    out.sort(key=lambda p: p[1], reverse=True)              # primary: age, descending
    return out

Using stability on purpose

Letter-logs go first, ordered by content and then identifier; digit-logs keep their original relative order. Giving every digit-log the same key lets the stable sort preserve their order:

def reorder_logs(logs: list[str]) -> list[str]:
    def key(log: str) -> tuple:
        ident, rest = log.split(" ", 1)
        if rest[0].isdigit():
            return (1,)  # all digit-logs tie, so stability keeps their order
        return (0, rest, ident)

    return sorted(logs, key=key)

A pairwise comparator

To form the largest number from a list of non-negative integers, put a before b when the concatenation a + b is larger than b + a. That rule compares two elements jointly, so it needs a comparator:

from functools import cmp_to_key


def largest_number(nums: list[int]) -> str:
    def order(a: str, b: str) -> int:
        if a + b > b + a:
            return -1  # a goes first
        if a + b < b + a:
            return 1
        return 0

    joined = "".join(sorted(map(str, nums), key=cmp_to_key(order)))
    return joined.lstrip("0") or "0"  # input of all zeros

Tie-breaking in a sweep line

The maximum number of half-open intervals [start, end) that overlap at one point (for example, meeting rooms needed). At equal times an end must be processed before a start, and the tuple (time, -1) already sorts before (time, 1):

def max_overlap(intervals: list[tuple[int, int]]) -> int:
    events = []
    for start, end in intervals:
        events.append((start, 1))
        events.append((end, -1))
    events.sort()  # same time: -1 (end) before +1 (start)
    best = current = 0
    for _, delta in events:
        current += delta
        best = max(best, current)
    return best

C++ library calls

#include <algorithm>
#include <string>
#include <vector>

struct Person {
  std::string name;
  int age;
};

// Older first, ties by name. Strict weak ordering: never use <= or >= here.
bool before(const Person& a, const Person& b) {
  if (a.age != b.age) return a.age > b.age;
  return a.name < b.name;
}

std::vector<Person> by_age_then_name(std::vector<Person> people) {
  std::sort(people.begin(), people.end(), before);
  return people;
}

int kth_smallest(std::vector<int> v, int k) {  // k is 0-based
  std::nth_element(v.begin(), v.begin() + k, v.end());
  return v[k];  // everything before it is <=, everything after it is >=
}

std::vector<int> smallest_k_sorted(std::vector<int> v, int k) {
  std::partial_sort(v.begin(), v.begin() + k, v.end());
  return std::vector<int>(v.begin(), v.begin() + k);
}

Complexity

• Library sorts: O(n log n) time. Python and Java object sorts need O(n) extra memory; std::sort uses O(log n) stack.
• A key function is evaluated n times; a comparator is called O(n log n) times, so keep it cheap and prefer keys when possible.
• std::nth_element is O(n) on average, std::partial_sort O(n log k). In Python, heapq.nsmallest(k, xs) and heapq.nlargest are O(n log k).
• max_overlap is O(n log n) for the sort plus O(n) for the sweep.

Common pitfalls

• Comparator returns a boolean in Python's cmp_to_key. True and False read as 1 and 0, so "less than" is never reported and the order is wrong.
• Comparing by subtraction (a - b) in Java or C overflows for large values. Use Integer.compare(a, b) or explicit comparisons.
• Non-strict comparators in C++: <= or a comparator that reads values that change during sorting (such as distances being updated elsewhere) is undefined behavior.
• list.sort() returns None. Writing x = x.sort() loses the list.
• Strings of digits sort lexicographically: "10" < "9". Convert to integers, or sort by (len(s), s) for non-negative numbers without leading zeros.
• Case and accents: use key=str.lower (or str.casefold) when the order should ignore case.
• NaN in float keys breaks the ordering; filter it out first.
• Assuming std::sort is stable. Use std::stable_sort or add a tiebreaker such as the original index.

Interview variations

• Largest number: the pairwise comparator above.
• Custom sort string: build rank = {ch: i for i, ch in enumerate(order)} and sort by rank.get(ch, len(order)).
• Sort by frequency, reorder log files, sort people by height: tuple keys plus stability.
• Meeting rooms II and car pooling: sort events with the right tie-break, then sweep.
• Group anagrams: "".join(sorted(word)) as a dictionary key (or a 26-count tuple for O(L) per word).
• Rank transform of an array: sort the distinct values once and map each value to its index.
• Contains duplicate within a sorted copy and minimum difference between elements: sort, then compare neighbors.