CATEGORY 8 OF 13

Sorting & Comparators

Learn built-in sort APIs, custom comparators, sort stability, and sort-then-scan patterns that simplify problems by imposing order on data.

Time: O(n log n) for comparison-based sorts

Space: O(n) for merge sort, O(log n) for quicksort stack depth

Learn & Reference

Understanding the Pattern

Sorting & Comparators

Sorting is one of the most powerful preprocessing steps in programming. Many problems that seem complex become straightforward once the data is in order. Understanding how to use built-in sort APIs, write custom comparators, and apply sort-then-scan patterns is essential for both interviews and real-world code.

Built-in Sort APIs

Every language provides a highly optimized sort function. These built-in sorts use hybrid algorithms (Timsort in Python/Java/JavaScript, Introsort in Go/C++) that adapt to the structure of your data. They are almost always faster than anything you would write by hand.

Key facts about built-in sorts:

Python: sorted() returns a new list; list.sort() sorts in-place. Both use Timsort.
JavaScript/TypeScript: Array.sort() sorts in-place and converts elements to strings by default — always pass a comparator for numbers.
Java: Arrays.sort() uses dual-pivot quicksort for primitives and Timsort for objects. Collections.sort() uses Timsort.
Go: sort.Slice() and slices.SortFunc() use pattern-defeating quicksort (pdqsort).

Custom Comparators

A comparator tells the sort function how to order two elements. This is how you sort by custom criteria — by length, by a specific field, in reverse order, or by multiple keys.

Comparator contract: Given elements a and b:

Return negative if a should come before b
Return zero if a and b are equal
Return positive if a should come after b

Key functions (Python) vs comparators (other languages):

Python's key= parameter is often simpler — you provide a function that extracts a sort key, and Python compares keys naturally
Other languages use explicit comparator functions that compare two elements directly

Multi-key sorting

Sort by primary key first, then by secondary key for ties. This is extremely common in interviews:

Sort intervals by start time, then by end time
Sort people by age, then alphabetically by name
Sort files by size descending, then by name ascending

Sort Stability

A stable sort preserves the relative order of elements that compare as equal. This matters when:

You sort by one key, then sort again by another key — stability preserves the first sort for ties
You need deterministic output order in interviews

Stable: Python (Timsort), Java (Timsort for objects), JavaScript (Timsort in V8) Not guaranteed stable: Java (primitives use quicksort), Go (use slices.SortStableFunc for stability)

Sort-Then-Scan Patterns

The most common interview technique with sorting: sort the data first, then solve the problem with a single linear scan.

Pattern: Sort + one pass = O(n log n) total time

Examples:

Find duplicates: sort, then check adjacent elements
Merge intervals: sort by start, then merge overlapping pairs
Two sum (sorted): sort, then use two pointers
Meeting rooms: sort by start time, scan for conflicts
Largest number: sort with custom comparator, concatenate

Lambda / Anonymous Comparators

Modern languages support inline comparator definitions. This keeps sort logic close to where it is used:

Python: key=lambda x: x[1] or cmp_to_key(lambda a, b: ...)
JavaScript/TypeScript: arr.sort((a, b) => a - b)
Java: Arrays.sort(arr, (a, b) -> a[0] - b[0]) or Comparator.comparing(...)
Go: slices.SortFunc(s, func(a, b T) int { ... })

Common Sort Algorithms (Conceptual)

You rarely implement these from scratch, but understanding them helps explain complexity and behavior:

Insertion sort — O(n²) worst, O(n) on nearly-sorted data. Stable. Used inside Timsort for small subarrays.
Merge sort — O(n log n) always. Stable. O(n) extra space. Timsort is derived from merge sort.
Quicksort — O(n log n) average, O(n²) worst. Not stable. O(log n) stack space. Fast in practice due to cache efficiency.
Counting/Radix sort — O(n + k) or O(n * d). Not comparison-based. Useful when values have a small range.

Common Mistakes

JavaScript default sort is lexicographic: [10, 2, 1].sort() gives [1, 10, 2] — always use (a, b) => a - b for numbers
Comparator overflow with subtraction: a - b can overflow for large integers in Java/Go — use Integer.compare(a, b) or explicit conditionals instead
Forgetting stability requirements: if you need stable sort in Go, use slices.SortStableFunc explicitly
Sorting when a partial sort suffices: if you only need the k-th smallest element, use a heap or quickselect (O(n)) instead of full sort (O(n log n))
Mutating the input array unexpectedly: in-place sorts modify the original array — copy first if you need to preserve the original order
Not handling equal elements in comparators: a valid comparator must be consistent — if compare(a, b) < 0, then compare(b, a) > 0; violating this causes undefined behavior
Sorting objects without a clear key: always define exactly what field(s) you are sorting by before writing the comparator

When to Use

Return elements in sorted order or find the k-th largest/smallest

Merge overlapping intervals or find conflicts

Group adjacent duplicates or find duplicates efficiently

Two-pointer problems where input is not already sorted

Custom ordering requirements (by length, frequency, multiple keys)

Problems where brute force is O(n²) but sorting reduces it to O(n log n)

Arrange elements to form the largest/smallest number

Comparisons between pairs of elements (closest pair, minimum difference)

Any problem where imposing order on the data simplifies the logic

Template

1# --- Basic Sort ---
2nums = [3, 1, 4, 1, 5]
3nums.sort()                            # in-place ascending
4sorted_nums = sorted(nums)             # returns new sorted list
5
6# --- Sort with Custom Key ---
7words = ["banana", "apple", "cherry"]
8words.sort(key=len)                    # by length
9words.sort(key=lambda w: w[-1])        # by last character
10
11# --- Sort-Then-Scan Pattern ---
12def solve(nums):
13    nums.sort()                        # step 1: sort
14    result = []
15    for i in range(len(nums)):         # step 2: linear scan
16        # process sorted data
17        pass
18    return result
19
20# --- Descending Sort ---
21nums.sort(reverse=True)
22
23# --- Multi-key Sort ---
24pairs = [(1, 'b'), (2, 'a'), (1, 'a')]
25pairs.sort(key=lambda x: (x[0], x[1]))  # [(1, 'a'), (1, 'b'), (2, 'a')]

{ }

Syntax Reference

1# === Built-in Sort ===
2nums = [3, 1, 4, 1, 5]
3sorted_nums = sorted(nums)       # new list: [1, 1, 3, 4, 5]
4nums.sort()                       # in-place sort
5
6# === Reverse Sort ===
7sorted(nums, reverse=True)        # [5, 4, 3, 1, 1]
8nums.sort(reverse=True)
9
10# === Key Function ===
11sorted(words, key=len)            # sort by length
12sorted(words, key=str.lower)      # case-insensitive
13sorted(pairs, key=lambda x: x[1]) # sort by second element
14
15# === Multi-key Sort ===
16sorted(people, key=lambda x: (x.age, x.name))
17# age ascending, then name ascending for ties
18
19# === Custom Comparator (rare in Python) ===
20from functools import cmp_to_key
21def compare(a, b):
22    # return negative if a < b, 0 if equal, positive if a > b
23    return a - b
24sorted(nums, key=cmp_to_key(compare))
25
26# === Stable Sort ===
27# Python sort is always stable (Timsort)
28# Sort by secondary key first, then primary key
29data.sort(key=lambda x: x.name)   # secondary
30data.sort(key=lambda x: x.age)    # primary (stability preserves name order)

📋

Common Recipes

1# --- Sort-Then-Scan: Find Duplicates ---
2def find_duplicates(nums):
3    nums.sort()
4    result = []
5    for i in range(1, len(nums)):
6        if nums[i] == nums[i - 1]:
7            result.append(nums[i])
8    return result
9
10# --- Merge Overlapping Intervals ---
11def merge_intervals(intervals):
12    intervals.sort(key=lambda x: x[0])
13    merged = [intervals[0]]
14    for start, end in intervals[1:]:
15        if start <= merged[-1][1]:
16            merged[-1][1] = max(merged[-1][1], end)
17        else:
18            merged.append([start, end])
19    return merged
20
21# --- Sort by Multiple Keys ---
22def sort_students(students):
23    # Sort by grade descending, then by name ascending
24    return sorted(students, key=lambda s: (-s['grade'], s['name']))
25
26# --- Custom String Sort (Largest Number) ---
27from functools import cmp_to_key
28def largest_number(nums):
29    strs = list(map(str, nums))
30    strs.sort(key=cmp_to_key(lambda a, b: -1 if a+b > b+a else 1))
31    return ''.join(strs).lstrip('0') or '0'
32
33# --- Sort + Two Pointers: Minimum Difference ---
34def min_diff(nums):
35    nums.sort()
36    return min(nums[i+1] - nums[i] for i in range(len(nums) - 1))

O(n)

Complexity

Algorithm	Best	Average	Worst	Space	Stable?
Timsort (Python/JS/Java objects)	O(n)	O(n log n)	O(n log n)	O(n)	Yes
Introsort (C++/Go pdqsort)	O(n log n)	O(n log n)	O(n log n)	O(log n)	No
Dual-pivot Quicksort (Java primitives)	O(n log n)	O(n log n)	O(n²)	O(log n)	No
Merge sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes
Quicksort	O(n log n)	O(n log n)	O(n²)	O(log n)	No
Insertion sort	O(n)	O(n²)	O(n²)	O(1)	Yes
Counting sort	O(n + k)	O(n + k)	O(n + k)	O(k)	Yes
Radix sort	O(n × d)	O(n × d)	O(n × d)	O(n + k)	Yes

Watch Out

✗JavaScript default sort is lexicographic: `[10, 2, 1].sort()` gives `[1, 10, 2]` — always use `(a, b) => a - b` for numbers
✗Comparator overflow with subtraction: `a - b` can overflow for large integers in Java/Go — use `Integer.compare(a, b)` or explicit conditionals instead
✗Forgetting stability requirements: if you need stable sort in Go, use `slices.SortStableFunc` explicitly
✗Sorting when a partial sort suffices: if you only need the k-th smallest element, use a heap or quickselect (O(n)) instead of full sort (O(n log n))
✗Mutating the input array unexpectedly: in-place sorts modify the original array — copy first if you need to preserve the original order
✗Not handling equal elements in comparators: a valid comparator must be consistent — if `compare(a, b) < 0`, then `compare(b, a) > 0`; violating this causes undefined behavior
✗Sorting objects without a clear key: always define exactly what field(s) you are sorting by before writing the comparator

PRACTICE PROBLEMS

Basic Recursion

Matrix / 2D Basics