> ## Documentation Index
> Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt
> Use this file to discover all available pages before exploring further.

# Sorting & Custom Comparators

> Strategic sorting techniques and custom comparators for competitive programming

# 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**.

<Note>
  **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"
</Note>

***

## When Sorting Helps

<CardGroup cols={2}>
  <Card title="Enables Binary Search" icon="magnifying-glass">
    Find elements, count less/greater, find bounds.
  </Card>

  <Card title="Enables Two Pointers" icon="arrows-left-right">
    Pair elements from ends, merge operations.
  </Card>

  <Card title="Greedy Processing" icon="lightbulb">
    Process smallest/largest first, interval scheduling.
  </Card>

  <Card title="Reduces Complexity" icon="chart-line">
    Many O(n²) become O(n log n) with sorting.
  </Card>
</CardGroup>

***

## Sorting Fundamentals

### Basic Sorting

```cpp theme={null}
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

```cpp theme={null}
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

```cpp theme={null}
// 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

```cpp theme={null}
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.

```cpp theme={null}
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).

```cpp theme={null}
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):

```cpp theme={null}
// 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.

```cpp theme={null}
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](https://codeforces.com/problemset/problem/777/C)    |
| Div2A - Many sorting problems | 800-1000 | [Problemset](https://codeforces.com/problemset?tags=sortings) |

***

## Pattern: Custom Order for Greedy

**Problem**: Arrange elements to maximize/minimize some combined result.

**Example**: Concatenate numbers to form largest number.

```cpp theme={null}
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.

```cpp theme={null}
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

<Warning>
  **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)

  ```cpp theme={null}
  // 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;
  });
  ```
</Warning>

<Warning>
  **Mistake 2: Sorting Changes Index Mapping**
  If you need original indices, create pairs:

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

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

  ```cpp theme={null}
  vector<int> original = arr;
  sort(arr.begin(), arr.end());
  ```
</Warning>

***

## Practice Problems

### Beginner (800-1100)

| Problem             | Concept        | Link                                                       |
| ------------------- | -------------- | ---------------------------------------------------------- |
| Sort the Array      | Basic sort     | [CF 451B](https://codeforces.com/problemset/problem/451/B) |
| Cookies             | Sort + greedy  | [CF 129B](https://codeforces.com/problemset/problem/129/B) |
| Sereja and Suffixes | Sort + queries | [CF 368B](https://codeforces.com/problemset/problem/368/B) |

### Intermediate (1100-1400)

| Problem           | Concept               | Link                                                         |
| ----------------- | --------------------- | ------------------------------------------------------------ |
| Tasks             | Custom sort           | [CF 978F](https://codeforces.com/problemset/problem/978/F)   |
| Maximum in Window | Sort + sliding window | [CF 1041C](https://codeforces.com/problemset/problem/1041/C) |
| The Number Game   | Sorting strategy      | [CF 1370C](https://codeforces.com/problemset/problem/1370/C) |

### Advanced (1400-1600)

| Problem                     | Concept            | Link                                                       |
| --------------------------- | ------------------ | ---------------------------------------------------------- |
| Cloud of Hashtags           | Custom string sort | [CF 777C](https://codeforces.com/problemset/problem/777/C) |
| New Year and Original Order | Digit sorting      | [CF 908D](https://codeforces.com/problemset/problem/908/D) |

***

## Key Takeaways

<CardGroup cols={2}>
  <Card title="Sort First" icon="lightbulb">
    Many problems become trivial after sorting. Always consider it.
  </Card>

  <Card title="Custom Comparators" icon="code">
    Use lambdas for flexible, readable sorting logic.
  </Card>

  <Card title="Strict Weak Ordering" icon="triangle-exclamation">
    Comparator must use `<`, not `<=`. Violating this causes undefined behavior.
  </Card>

  <Card title="Preserve Indices" icon="list-ol">
    If you need original positions, pair elements with indices before sorting.
  </Card>
</CardGroup>

***

## Next Up

<Card title="Chapter 8: Recursion & Backtracking" icon="arrow-right" href="/courses/competitive-programming/08-recursion">
  Master the art of breaking problems into subproblems and exploring all possibilities systematically.
</Card>