Sorting & Custom Comparators

The Mental Model

Sorting is often the first step in solving a problem, not the solution itself. A sorted array enables binary search, two pointers, and greedy approaches. The key skill is knowing when to sort and how to define the sort order.

Pattern Recognition Signals:

Problem mentions “minimum” or “maximum”
Need to pair elements optimally
Need to process elements in a specific order
Two pointers would work “if only the array were sorted”

When Sorting Helps

Enables Binary Search

Find elements, count less/greater, find bounds.

Enables Two Pointers

Pair elements from ends, merge operations.

Greedy Processing

Process smallest/largest first, interval scheduling.

Reduces Complexity

Many O(n²) become O(n log n) with sorting.

Sorting Fundamentals

Basic Sorting

vector<int> arr = {5, 2, 8, 1, 9};

// Ascending (default)
sort(arr.begin(), arr.end());
// arr = {1, 2, 5, 8, 9}

// Descending
sort(arr.begin(), arr.end(), greater<int>());
// arr = {9, 8, 5, 2, 1}

// Partial sort (first k elements sorted)
partial_sort(arr.begin(), arr.begin() + 3, arr.end());
// First 3 elements are the 3 smallest, sorted

// Nth element (find kth smallest, O(n) average)
nth_element(arr.begin(), arr.begin() + k, arr.end());
// arr[k] is the (k+1)th smallest element

Sorting Pairs and Tuples

vector<pair<int, int>> pairs = {{3, 1}, {1, 2}, {1, 1}};

// Default: sort by first, then by second
sort(pairs.begin(), pairs.end());
// pairs = {{1, 1}, {1, 2}, {3, 1}}

// Sort by second element
sort(pairs.begin(), pairs.end(), [](auto& a, auto& b) {
    return a.second < b.second;
});
// pairs = {{3, 1}, {1, 1}, {1, 2}}

// Tuples sort lexicographically by default
vector<tuple<int, int, int>> v = {{1, 2, 3}, {1, 1, 4}, {0, 5, 5}};
sort(v.begin(), v.end());
// v = {{0, 5, 5}, {1, 1, 4}, {1, 2, 3}}

Custom Comparators: The Power Tool

Lambda Comparators

// Sort by absolute value
vector<int> arr = {-5, 2, -8, 1, 9};
sort(arr.begin(), arr.end(), [](int a, int b) {
    return abs(a) < abs(b);
});
// arr = {1, 2, -5, -8, 9}

// Sort strings by length, then lexicographically
vector<string> words = {"ab", "a", "abc", "b"};
sort(words.begin(), words.end(), [](const string& a, const string& b) {
    if (a.size() != b.size()) return a.size() < b.size();
    return a < b;
});
// words = {"a", "b", "ab", "abc"}

Struct with Custom Comparator

struct Event {
    int start, end, priority;
};

// Option 1: Lambda
vector<Event> events;
sort(events.begin(), events.end(), [](const Event& a, const Event& b) {
    return a.end < b.end;  // Sort by end time
});

// Option 2: Overload operator<
struct Event {
    int start, end, priority;
    
    bool operator<(const Event& other) const {
        return end < other.end;
    }
};
sort(events.begin(), events.end());  // Uses operator<

// Option 3: Separate comparator function
bool compareByStart(const Event& a, const Event& b) {
    return a.start < b.start;
}
sort(events.begin(), events.end(), compareByStart);

Pattern: Coordinate Compression

Problem: Values are large (up to 10⁹) but count is small (up to 10⁵). Solution: Map values to smaller range while preserving order.

vector<int> compress(vector<int>& arr) {
    vector<int> sorted = arr;
    sort(sorted.begin(), sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
    
    // Map each value to its rank
    vector<int> result(arr.size());
    for (int i = 0; i < arr.size(); i++) {
        result[i] = lower_bound(sorted.begin(), sorted.end(), arr[i]) 
                    - sorted.begin();
    }
    
    return result;
}

// Example: arr = {100, 5, 100, 3, 1000}
// Compressed: {1, 1, 1, 0, 2}  (0-indexed ranks)

Use Cases: Segment trees, BIT when values are too large.

Pattern: Sorting by Multiple Criteria

Problem: Sort students by grade (descending), then by name (ascending).

struct Student {
    string name;
    int grade;
};

vector<Student> students;

sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
    if (a.grade != b.grade) {
        return a.grade > b.grade;  // Higher grade first
    }
    return a.name < b.name;  // Alphabetically for same grade
});

Alternative using tuples (for complex sorting):

// Sort by (-grade, name) lexicographically
sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
    return make_tuple(-a.grade, a.name) < make_tuple(-b.grade, b.name);
});

Pattern: Interval Scheduling

Problem: Select maximum number of non-overlapping intervals. Key Insight: Sort by end time. Greedy works because finishing early leaves room for more.

int maxNonOverlapping(vector<pair<int, int>>& intervals) {
    // Sort by end time
    sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) {
        return a.second < b.second;
    });
    
    int count = 0;
    int lastEnd = INT_MIN;
    
    for (auto& [start, end] : intervals) {
        if (start >= lastEnd) {
            count++;
            lastEnd = end;
        }
    }
    
    return count;
}

Codeforces Problems:

Problem	Rating	Link
Cloud of Hashtags	1300	CF 777C
Div2A - Many sorting problems	800-1000	Problemset

Pattern: Custom Order for Greedy

Problem: Arrange elements to maximize/minimize some combined result. Example: Concatenate numbers to form largest number.

string largestNumber(vector<int>& nums) {
    vector<string> strs;
    for (int n : nums) strs.push_back(to_string(n));
    
    // Key insight: compare "ab" vs "ba"
    sort(strs.begin(), strs.end(), [](const string& a, const string& b) {
        return a + b > b + a;
    });
    
    if (strs[0] == "0") return "0";  // All zeros
    
    string result;
    for (const string& s : strs) result += s;
    return result;
}

// Example: [3, 30, 34] → "34330"

Stable Sort

When: You need to preserve relative order of equal elements.

vector<pair<int, string>> data = {{3, "a"}, {1, "b"}, {3, "c"}, {1, "d"}};

stable_sort(data.begin(), data.end(), [](auto& a, auto& b) {
    return a.first < b.first;
});
// data = {{1, "b"}, {1, "d"}, {3, "a"}, {3, "c"}}
// Notice: "b" before "d" and "a" before "c" (original order preserved)

Common Mistakes

Mistake 1: Inconsistent Comparator Comparator must define a strict weak ordering:

a < a must be false (irreflexivity)
If a < b then b < a must be false (antisymmetry)
If a < b and b < c then a < c (transitivity)

// WRONG: Can cause undefined behavior
sort(arr.begin(), arr.end(), [](int a, int b) {
    return a <= b;  // Using <= instead of <
});

// CORRECT
sort(arr.begin(), arr.end(), [](int a, int b) {
    return a < b;
});

Mistake 2: Sorting Changes Index Mapping If you need original indices, create pairs:

vector<pair<int, int>> indexed(n);
for (int i = 0; i < n; i++) {
    indexed[i] = {arr[i], i};
}
sort(indexed.begin(), indexed.end());

Mistake 3: Forgetting That Sort Modifies Array If you need the original, copy first:

vector<int> original = arr;
sort(arr.begin(), arr.end());

Practice Problems

Beginner (800-1100)

Problem	Concept	Link
Sort the Array	Basic sort	CF 451B
Cookies	Sort + greedy	CF 129B
Sereja and Suffixes	Sort + queries	CF 368B

Intermediate (1100-1400)

Problem	Concept	Link
Tasks	Custom sort	CF 978F
Maximum in Window	Sort + sliding window	CF 1041C
The Number Game	Sorting strategy	CF 1370C

Advanced (1400-1600)

Problem	Concept	Link
Cloud of Hashtags	Custom string sort	CF 777C
New Year and Original Order	Digit sorting	CF 908D

Key Takeaways

Sort First

Many problems become trivial after sorting. Always consider it.

Custom Comparators

Use lambdas for flexible, readable sorting logic.

Strict Weak Ordering

Comparator must use <, not <=. Violating this causes undefined behavior.

Preserve Indices

If you need original positions, pair elements with indices before sorting.

Next Up

Chapter 8: Recursion & Backtracking

Master the art of breaking problems into subproblems and exploring all possibilities systematically.

Getting Started

Fundamental Patterns

Greedy & Divide and Conquer

Dynamic Programming

Graph Algorithms

Advanced Topics

Contest Mastery

Sorting & Custom Comparators

Sorting & Custom Comparators

The Mental Model

When Sorting Helps

Enables Binary Search

Enables Two Pointers

Greedy Processing

Reduces Complexity

Sorting Fundamentals

Basic Sorting

Sorting Pairs and Tuples

Custom Comparators: The Power Tool

Lambda Comparators

Struct with Custom Comparator

Pattern: Coordinate Compression

Pattern: Sorting by Multiple Criteria

Pattern: Interval Scheduling

Pattern: Custom Order for Greedy

Stable Sort

Common Mistakes

Practice Problems

Beginner (800-1100)

Intermediate (1100-1400)

Advanced (1400-1600)

Key Takeaways

Sort First

Custom Comparators

Strict Weak Ordering

Preserve Indices

Next Up

Chapter 8: Recursion & Backtracking

​Sorting & Custom Comparators

​The Mental Model

​When Sorting Helps

Enables Binary Search

Enables Two Pointers

Greedy Processing

Reduces Complexity

​Sorting Fundamentals

​Basic Sorting

​Sorting Pairs and Tuples

​Custom Comparators: The Power Tool

​Lambda Comparators

​Struct with Custom Comparator

​Pattern: Coordinate Compression

​Pattern: Sorting by Multiple Criteria

​Pattern: Interval Scheduling

​Pattern: Custom Order for Greedy

​Stable Sort

​Common Mistakes

​Practice Problems

​Beginner (800-1100)

​Intermediate (1100-1400)

​Advanced (1400-1600)

​Key Takeaways

Sort First

Custom Comparators

Strict Weak Ordering

Preserve Indices

​Next Up

Chapter 8: Recursion & Backtracking

Sorting & Custom Comparators

The Mental Model

When Sorting Helps

Sorting Fundamentals

Basic Sorting

Sorting Pairs and Tuples

Custom Comparators: The Power Tool

Lambda Comparators

Struct with Custom Comparator

Pattern: Coordinate Compression

Pattern: Sorting by Multiple Criteria

Pattern: Interval Scheduling

Pattern: Custom Order for Greedy

Stable Sort

Common Mistakes

Practice Problems

Beginner (800-1100)

Intermediate (1100-1400)

Advanced (1400-1600)

Key Takeaways

Next Up