Using sort() and Built-in Tools

Real-world analogy

What is it?

C++ provides powerful built-in sorting and searching tools that every competitive programmer must know. The sort() function sorts data in O(n log n) time, while lower_bound and upper_bound perform binary searches on sorted data in O(log n). Mastering these tools means you spend less time writing code and more time solving problems.

Real-world relevance

Every app you use relies on sorting: your email inbox sorted by date, your music playlist sorted by artist, search results sorted by relevance, leaderboards sorted by score. The fast sorting algorithms behind sort() (like QuickSort and MergeSort) were invented decades ago and are still the backbone of every modern system.

Key points

• The C++ sort() Function — C++ gives us sort() from the header (included in bits/stdc++.h). For arrays: sort(arr, arr + n). For vectors: sort(v.begin(), v.end()). It sorts in ascending order by default and is extremely fast — O(n log n).
• Sorting a Vector — vector v = {5, 2, 8, 1, 9}; sort(v.begin(), v.end()); Now v is {1, 2, 5, 8, 9}. The begin() and end() functions return iterators (think of them as pointers) to the start and one-past-the-end of the vector.
• Sorting in Reverse (Descending) — To sort largest to smallest, use: sort(v.begin(), v.end(), greater()). Or sort normally and then reverse: sort(v.begin(), v.end()); reverse(v.begin(), v.end()). Both give descending order.
• Custom Comparators — You can tell sort() exactly HOW to compare. Write a function: bool cmp(int a, int b) { return a > b; } Then use: sort(v.begin(), v.end(), cmp). Return true if a should come before b. This lets you sort by any criteria you want!
• Sorting Strings — sort() works on strings too! It sorts them alphabetically (lexicographic order). vector names = {"Charlie", "Alice", "Bob"}; sort(names.begin(), names.end()); gives {"Alice", "Bob", "Charlie"}.
• lower_bound — Find First >= — lower_bound(v.begin(), v.end(), x) returns an iterator to the first element that is >= x. It uses binary search internally, so the data must be sorted. If x is not in the array, it points to where x would be inserted.
• upper_bound — Find First > — upper_bound(v.begin(), v.end(), x) returns an iterator to the first element that is strictly > x. Together with lower_bound, you can find exactly how many times a value appears: count = upper_bound - lower_bound.
• Sorting Pairs — sort() on a vector> sorts by first element, then by second if first elements are equal. This is incredibly useful in CP for sorting by multiple criteria: pair.first for primary sort, pair.second for tiebreaker.
• Why sort() Beats Bubble Sort — C++ sort() uses IntroSort, which combines QuickSort, HeapSort, and InsertionSort. It runs in O(n log n), which is MUCH faster than bubble sort's O(n^2). For 100,000 elements: sort() does about 1.7 million operations, bubble sort does 10 billion!

Code example

#include <bits/stdc++.h>
using namespace std;

bool descending(int a, int b) {
    return a > b; // Returns true if a should come before b
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Sort a vector
    vector<int> v = {5, 2, 8, 1, 9, 2, 8, 3};
    sort(v.begin(), v.end());
    cout << "Ascending: ";
    for (int x : v) cout << x << " ";
    cout << "\n";

    // Sort descending
    sort(v.begin(), v.end(), descending);
    cout << "Descending: ";
    for (int x : v) cout << x << " ";
    cout << "\n";

    // Sort ascending again for binary search
    sort(v.begin(), v.end());

    // lower_bound and upper_bound
    auto lo = lower_bound(v.begin(), v.end(), 2);
    auto hi = upper_bound(v.begin(), v.end(), 2);
    cout << "First 2 at index: " << (lo - v.begin()) << "\n";
    cout << "Count of 2s: " << (hi - lo) << "\n";

    // Sorting pairs
    vector<pair<int,int>> scores = {{90, 1}, {85, 3}, {90, 2}};
    sort(scores.begin(), scores.end());
    cout << "Sorted pairs: ";
    for (auto p : scores) cout << "(" << p.first << "," << p.second << ") ";
    cout << "\n";

    return 0;
}

Line-by-line walkthrough

1. 1. sort(v.begin(), v.end()); — this sorts the entire vector v in ascending order. begin() points to the first element and end() points just past the last element. This range notation is standard in C++ STL.
2. 2. sort(v.begin(), v.end(), descending); — here we pass our custom comparison function. It tells sort() that a should come before b when a > b, resulting in descending order.
3. 3. auto lo = lower_bound(v.begin(), v.end(), 2); — lower_bound uses binary search to find the first element >= 2. The 'auto' keyword lets C++ figure out the iterator type for us.
4. 4. auto hi = upper_bound(v.begin(), v.end(), 2); — upper_bound finds the first element > 2. The elements between lo and hi are all equal to 2.
5. 5. (hi - lo) — subtracting two iterators gives the number of elements between them. This tells us how many times 2 appears in the sorted vector.
6. 6. vector> scores — pairs are sorted by first element, then second. So (85,3) comes before (90,1), and (90,1) comes before (90,2).

Spot the bug

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {5, 3, 1, 4, 2};

    // Find the value 3 using lower_bound
    auto it = lower_bound(v.begin(), v.end(), 3);
    if (it != v.end() && *it == 3) {
        cout << "Found 3 at index " << (it - v.begin()) << "\n";
    } else {
        cout << "3 not found\n";
    }

    return 0;
}

Explain like I'm 5

Fun fact

Hands-on challenge

More resources

• C++ sort() Reference (cplusplus.com)
• Sorting in C++ STL (YouTube)
• Sorting and Searching Problems (CSES)