Skip to content
Hari KharelStudy

Sorting and custom comparators

coreCommon atGoogleMetaAmazonStripeAnthropicRead firstComplexity analysisRecursionPractise in the Sandbox →

Sorting puts items in order so that equal or close things end up next to each other, which turns many search problems into one linear scan. Library sorts are O(n log n), and no comparison sort can do better. In interviews you’ll rarely write a sort from scratch, but you’ll constantly write comparators (sort by several keys, some descending) and need to know whether your sort is stable (equal items keep their input order).

The idea in plain words

Section titled “The idea in plain words”

Think of a shuffled deck of cards. Once it’s sorted, questions that were hard become easy. “Are there two of the same card?” Just look at neighbours. “What’s the 10th smallest?” Look at position 10. “Which cards are between 5 and 9?” They sit in one contiguous block.

That is the real reason sorting shows up in interviews: sort first, then scan turns an O(n²) “compare everything with everything” into O(n log n) + O(n).

There are two classic ways to sort by comparing, and they are mirror images:

  • Merge sort does the easy part first: split in half without looking at anything, sort both halves, then do the real work while merging two sorted lists.
  • Quicksort does the hard part first: partition around a pivot so everything smaller is on the left, then sort both sides. Joining them back needs no work at all.

Both are divide and conquer. Both take O(n log n) when the halves are balanced.

See it

Section titled “See it”

Pick an algorithm, edit the values, and step through. Things to try:

  • Merge sort on any input uses about the same number of comparisons. Its recursion is always balanced.
  • Quicksort with “last element” pivot on the sorted preset makes the most lopsided split possible every time. Count the comparisons, then switch the pivot to random.
  • Insertion sort on sorted vs reversed: n − 1 comparisons vs n(n−1)/2.
Watch a comparison sort
step through
38
27
43
3
9
82
10
55
19
64
comparisons0
writes0
range being sortedjust writtenfinaloutside the range
Merge sort: split the array in half, sort each half, then merge the two sorted halves. Splitting stops at single elements, which are already sorted.
1 / 50

When to reach for it

Section titled “When to reach for it”
The problem says… Why sorting fits
“find duplicates / closest pair / anything about neighbours” After sorting, related items are adjacent; one scan finds them.
“pairs or triples that…” on a list where order doesn’t matter Sorting enables two pointers moving inward.
“order by X, then by Y descending, ties by name” That’s a multi-key comparator. Get the tie-breaking exactly right.
“process events / intervals in time order” Sort by start time, then sweep.
“smallest value such that…”, “how many are ≤ x” Sort once, then binary search per query.
“top k” or “k-th smallest” Sorting works (O(n log n)); a heap (O(n log k)) or quickselect (O(n) expected) is better. Mention both.

How it works

Section titled “How it works”

Merge sort

Section titled “Merge sort”
  1. If the list has 0 or 1 items, it’s sorted. Return it.
  2. Split it in half and sort each half recursively.
  3. Merge: compare the front of each half, take the smaller, repeat. On a tie, take from the left half; this one rule is what makes merge sort stable.
  4. When one half runs out, copy the rest of the other half.
merge_sort.py
def merge_sort(xs: list[int]) -> list[int]:
    """Stable O(n log n) sort. Returns a new list; O(n) extra space."""
    if len(xs) <= 1:                    # 1. a list of 0 or 1 items is already sorted
        return xs[:]
    mid = len(xs) // 2
    left = merge_sort(xs[:mid])         # 2. sort each half recursively
    right = merge_sort(xs[mid:])
    out: list[int] = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:         # 3. merge: <= takes from the LEFT on ties (stable)
            out.append(left[i])
            i += 1
        else:
            out.append(right[j])
            j += 1
    out.extend(left[i:])                # 4. one side ran out; copy the rest of the other
    out.extend(right[j:])
    return out




if __name__ == "__main__":
    assert merge_sort([5, 2, 4, 6, 1, 3]) == [1, 2, 3, 4, 5, 6]
    assert merge_sort([]) == []
    assert merge_sort([3, 3, -1, 0]) == [-1, 0, 3, 3]
    data = [9, 7, 5, 3, 1, 2, 4, 6, 8, 0]
    assert merge_sort(data) == sorted(data) and data[0] == 9  # input untouched
    print("ok")

Quicksort (Lomuto partition)

Section titled “Quicksort (Lomuto partition)”
  1. Pick a pivot. A random pivot makes the bad case vanishingly unlikely on any input. Park it at the end.
  2. Scan left to right with j. Keep the invariant: everything in [lo..i-1] is smaller than the pivot. When xs[j] is smaller, swap it to position i and advance i.
  3. Swap the pivot into position i. It is now in its final position.
  4. Recurse on the left part and the right part.
quicksort.py
import random




def partition(xs: list[int], lo: int, hi: int) -> int:
    """Lomuto partition of xs[lo..hi] around a random pivot. Returns the pivot's final index."""
    p = random.randint(lo, hi)
    xs[p], xs[hi] = xs[hi], xs[p]      # 1. random pivot, parked at the end
    pivot = xs[hi]
    i = lo                             # 2. invariant: xs[lo..i-1] < pivot, xs[i..j-1] >= pivot
    for j in range(lo, hi):
        if xs[j] < pivot:
            xs[i], xs[j] = xs[j], xs[i]  # grow the "small" region by one
            i += 1
    xs[i], xs[hi] = xs[hi], xs[i]      # 3. drop the pivot between the two regions
    return i




def quicksort(xs: list[int], lo: int = 0, hi: int | None = None) -> None:
    """In-place, expected O(n log n), not stable."""
    if hi is None:
        hi = len(xs) - 1
    if lo >= hi:
        return
    m = partition(xs, lo, hi)
    quicksort(xs, lo, m - 1)           # 4. the pivot is final; recurse on each side
    quicksort(xs, m + 1, hi)




if __name__ == "__main__":
    for _ in range(200):
        data = [random.randint(-5, 5) for _ in range(random.randint(0, 12))]
        want = sorted(data)
        quicksort(data)
        assert data == want
    print("ok")

Stability and multi-key sorting

Section titled “Stability and multi-key sorting”

A sort is stable if items that compare equal come out in the same relative order they went in. It matters as soon as records have more than one field.

Stable vs unstable: what happens to ties
interactive
input (#: original position)
#0Leered3
#1Anablue5
#2Maxred5
#3Idablue3
#4Bored4
#5Cyblue5
#6Evered3
#7Gusblue4
output, points high → low
#1Anablue5
#2Maxred5
#5Cyblue5
#4Bored4
#7Gusblue4
#0Leered3
#3Idablue3
#6Evered3
tie group in the expected ordertie group reordered
Merge sort / Timsort / LINQ OrderBy / JS sort: ties keep their input order. Every tie group came out in the expected order.

Stability gives you a second way to sort by several keys: sort by the least important key first, then stably by the more important ones. Each later pass keeps the earlier order inside its ties. This is how spreadsheets sort when you click column headers one after another.

Most of the time, though, you write one comparator that checks keys in order:

  1. Compare by the primary key. If they differ, that decides it.
  2. Otherwise compare by the secondary key, flipping the sign for descending.
  3. Keep going until a key differs. A final unique key (an id or name) makes the order fully deterministic, even with an unstable sort.
comparators.py
from dataclasses import dataclass
from functools import cmp_to_key




@dataclass(frozen=True)
class Emp:
    name: str
    dept: str
    salary: int




STAFF = [Emp("Kai", "ops", 90), Emp("Ana", "eng", 120), Emp("Bo", "eng", 120),
         Emp("Cy", "ops", 95), Emp("Di", "eng", 100)]
WANT = ["Ana", "Bo", "Di", "Cy", "Kai"]  # dept asc, salary desc, name asc


# 1. Key tuple: compared left to right. Negate a number to flip its direction.
by_key = sorted(STAFF, key=lambda e: (e.dept, -e.salary, e.name))


# 2. Stable multi-pass: sort by the LEAST important key first. Works for keys you can't negate.
passes = sorted(STAFF, key=lambda e: e.name)
passes.sort(key=lambda e: e.salary, reverse=True)  # reverse=True keeps ties stable too
passes.sort(key=lambda e: e.dept)




# 3. Old-style comparator: negative, zero or positive. Wrap it with cmp_to_key.
def cmp(a: Emp, b: Emp) -> int:
    if a.dept != b.dept:
        return -1 if a.dept < b.dept else 1
    if a.salary != b.salary:
        return b.salary - a.salary          # descending: b before a
    return (a.name > b.name) - (a.name < b.name)




by_cmp = sorted(STAFF, key=cmp_to_key(cmp))


if __name__ == "__main__":
    for result in (by_key, passes, by_cmp):
        assert [e.name for e in result] == WANT
    print("ok")

What each language gives you

Section titled “What each language gives you”
Python TypeScript / JS C#
In place xs.sort(key=…, reverse=…) xs.sort((a, b) => …) Array.Sort(xs, cmp), list.Sort(cmp)
New copy sorted(xs, key=…) xs.toSorted(cmp) (ES2023), or [...xs].sort(cmp) LINQ xs.OrderBy(…).ThenBy(…)
Stable? yes (Timsort) yes, required since ES2019 Array.Sort / List.Sort: no (introsort). LINQ OrderBy: yes
Comparator style a key function returning a tuple; functools.cmp_to_key for a two-argument function two-argument function returning negative / 0 / positive Comparison<T>, IComparer<T>, Comparer<T>.Create, or a key selector in LINQ
Descending reverse=True, or negate a numeric key swap a and b OrderByDescending, or b.CompareTo(a)
Default string order code point UTF-16 code unit, even for numbers culture-sensitive; pass StringComparer.Ordinal for code-point order

What it costs

Section titled “What it costs”
Algorithm Best Average Worst Extra space Stable
Merge sort n log n n log n n log n O(n) yes
Quicksort (random pivot) n log n n log n n² (vanishingly rare) O(log n) stack no
Heapsort n log n n log n n log n O(1) no
Insertion sort n (already sorted) n² n² O(1) yes
Timsort (Python, V8) n (already sorted) n log n n log n O(n) yes
Introsort (.NET Array.Sort) n log n n log n n log n O(log n) no
Counting sort (keys in 0..k) n + k n + k n + k O(n + k) yes

Why n log n? Merge sort splits log₂ n times until pieces have size 1, and every level of merging touches all n items once: n work × log n levels.

Why you can’t beat it by comparing. There are n! possible orderings of n items, and each comparison has two outcomes, so it can at best halve the remaining possibilities. You need at least log₂(n!) ≈ n log₂ n − 1.44n comparisons. To go faster you must use something other than comparisons, such as the values themselves (counting sort, radix sort) when keys are small integers.

Comparing isn’t always O(1). Sorting n strings of length L costs O(L · n log n) in the worst case, because each comparison may read the whole string.

n log n is close to linear; n² is not
drag n
1.0k2.0k3.1k4.1kinput size n →
n = 16
O(n): 16 opsO(n log n): 64 opsO(n²): 256 ops

Variations you’ll meet

Section titled “Variations you’ll meet”
  • Sort indices, not values. Sort range(n) by xs[i] to keep track of where each value came from (an “argsort”).
  • Sort by a derived key. Absolute value, length, distance from a point, a day-of-week index. Compute the key once (Python’s key= does this for you; in JS, precompute into pairs if the key is expensive).
  • Counting / bucket sort. When keys are small integers (ages, scores 0–100, letters), count occurrences: O(n + k), no comparisons.
  • Partial sorting. Only need the top k? A heap of size k is O(n log k). Only need the k-th? Quickselect is O(n) expected; see divide and conquer.
  • External sorting. Data bigger than memory: sort chunks that fit, write them out, then k-way merge them with a heap.
  • Custom orders that aren’t “by a field”. Example: arrange numbers to form the largest concatenation; the comparator is “does a + b beat b + a as strings?”. The comparator must still be consistent (transitive), or the result is undefined.

Pitfalls

Section titled “Pitfalls”
  • JavaScript’s default sort is by string. [10, 9, 1].sort() gives [1, 10, 9]. Always pass (a, b) => a - b for numbers.
  • Returning a boolean from a JS comparator. (a, b) => a > b returns true/false, which become 1/0. It never says “less than” and sorts incorrectly. Return a negative, zero or positive number.
  • a - b overflow in C#. With int keys near the limits, subtraction overflows and flips the sign. Use a.CompareTo(b).
  • Assuming C# Array.Sort is stable. It isn’t. Use LINQ OrderBy or add a final tie-breaker key.
  • Culture-sensitive string comparison. C# string.CompareTo and JS localeCompare follow locale rules (case, accents), which may not match what tests expect. Use ordinal comparison unless you want human ordering.
  • Inconsistent comparators. A comparator that says a < b, b < c and c < a (or isn’t symmetric) can cause wrong output or even exceptions (.NET may throw “IComparer.Compare() method returns inconsistent results”).
  • Sorting inside a loop. Re-sorting after every insert is O(n² log n). Keep a heap or sorted container instead.
  • Mutating the caller’s data. list.sort() and JS sort() work in place. If the problem says “don’t modify the input”, copy first.

In the interview

Section titled “In the interview”
  • Say what sorting buys you before you do it: “Sorting costs n log n, but then duplicates are adjacent and I can finish in one pass.”
  • State the tie-breaking rule out loud and check it against the examples. Most comparator bugs are in the tie case.
  • Mention stability when records have several fields: “I’m using a stable sort, so equal scores keep their input order.”
  • Know the library’s guarantees for your language: stability, in-place vs copy, the default string order.
  • Expect follow-ups: “Can you avoid the n log n?” (counting sort, heap for top-k, quickselect), “What if the data doesn’t fit in memory?” (external merge sort), “What’s quicksort’s worst case and how do you avoid it?” (random pivot, introsort), “Is your sort stable?”.

Check yourself

Section titled “Check yourself”
Check yourself
pick one
You sort records by city with a stable sort, then sort the result by age with a stable sort. What order do you get?
Check yourself
pick one
Quicksort always picks the first element as the pivot. Which input makes it slowest?
Check yourself
pick one
Why can't any comparison-based sort guarantee fewer than about n log n comparisons?

Practice on your own

Section titled “Practice on your own”

These are classic textbook exercises, not gym questions:

  • Sort an array of 0s, 1s and 2s in a single pass and O(1) space (Dutch national flag).
  • Arrange a list of non-negative integers to form the largest possible number when concatenated.
  • Sort the characters of a string by how often they occur, most frequent first, ties alphabetical.
  • Compute a researcher’s h-index from a list of citation counts.
  • Implement merge sort bottom-up (iteratively, merging runs of 1, 2, 4, …) with no recursion.

Go deeper

Section titled “Go deeper”
Section titled “Related”
Two pointersWhat sorted input makes possible in one linear pass.
Binary searchAnswer many queries against one sorted array.
Heaps and priority queuesTop-k and repeated min/max without a full sort.
Divide and conquerThe recursion pattern behind merge sort and quicksort.