Back to all concepts
Intermediate 12 min

Sorting and Searching

Master STL sorting and searching algorithms with custom comparators and understand their performance characteristics

Master the highly optimized STL sorting and searching algorithms that outperform most hand-written implementations.

A Simple Example 

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> numbers{5, 2, 8, 1, 9, 3, 7};

    // Sort in ascending order
    std::sort(numbers.begin(), numbers.end());
    std::cout << "Sorted: ";
    for (int n : numbers) std::cout << n << " ";
    std::cout << "\n";

    // Sort in descending order
    std::sort(numbers.begin(), numbers.end(), std::greater<int>());
    std::cout << "Descending: ";
    for (int n : numbers) std::cout << n << " ";
    std::cout << "\n";

    // Partial sort - only sort first 3 elements
    std::vector<int> data{9, 7, 5, 3, 1, 2, 4, 6, 8};
    std::partial_sort(data.begin(), data.begin() + 3, data.end());
    std::cout << "Top 3: ";
    for (int i{0}; i < 3; ++i) std::cout << data[i] << " ";
    std::cout << "\n";

    // Binary search (requires sorted data)
    std::vector<int> sorted{1, 2, 3, 5, 7, 8, 9};
    bool found = std::binary_search(sorted.begin(), sorted.end(), 5);
    std::cout << "Found 5: " << std::boolalpha << found << "\n";

    return 0;
}

Breaking It Down

std::sort - The Workhorse

  • What it is: Highly optimized O(n log n) sorting algorithm
  • Uses introsort: hybrid of quicksort, heapsort, and insertion sort
  • Not stable - equal elements may be reordered
  • Use for: Most general-purpose sorting needs

Custom Comparators

  • What it is: Function/functor defining custom ordering
  • std::greater<T>() for descending order
  • Lambda: [](int a, int b) { return a > b; }
  • Remember: Comparator should return true if a comes before b

Binary Search Family

  • binary_search(): Returns bool, O(log n)
  • lower_bound(): First element NOT less than value
  • upper_bound(): First element GREATER than value
  • Remember: All require sorted data!

lower_bound and upper_bound

  • lower_bound(val): First element >= val (could be equal)
  • upper_bound(val): First element > val (definitely greater)
  • Together: [lower_bound, upper_bound) gives range of equal elements
  • Remember: Return iterators, not bools or values

Why This Matters

  • Sorting and searching are fundamental operations in programming.
  • std::sort() uses highly optimized algorithms (typically introsort - a hybrid of quicksort, heapsort, and insertion sort) that outperform most hand-written sorts.
  • Understanding these algorithms and their guarantees helps you write correct, efficient code.

Critical Insight

lower_bound() and upper_bound() are incredibly powerful for range queries on sorted data.

lower_bound(value) gives you the first element that's NOT less than value - this could be equal or greater.

upper_bound(value) gives you the first element that's GREATER than value.

Together, they give you all elements equal to value in O(log n) time! Think of them as binary search that tells you WHERE the value is or WHERE it should be inserted.

Best Practices

Always use std::sort over hand-written sorts: It's highly optimized and handles edge cases correctly.

Check if data is sorted before binary search: All binary search variants require sorted data or results are undefined.

Use partial_sort for "top N" queries: More efficient than sorting everything when you only need the first few.

Prefer lower_bound over binary_search for position: When you need to know where to insert, not just if it exists.

Common Mistakes

Using binary search on unsorted data: All binary search variants (binary_search, lower_bound, upper_bound) require sorted data.

Wrong comparator for lower_bound: When using lower_bound with custom comparator, make sure the comparator matches the sort order.

Confusing lower_bound and upper_bound: lower_bound finds >= value, upper_bound finds > value. Easy to mix up!

Debug Challenge

This code needs to find if a value exists in a sorted array efficiently. Click the highlighted line to fix it:

1 #include <algorithm>
2 #include <vector>
3
4 int main() {
5 std::vector<int> sorted{1, 3, 5, 7, 9};
6 for (int n : sorted) {
7 if (n == 5) found = true;
8 }
9 return 0;
10 }

Quick Quiz

  1. What's the time complexity of std::sort()?
O(n log n)
O(n)
O(n²)
  1. What's the difference between sort() and stable_sort()?
stable_sort preserves the relative order of equal elements
stable_sort is faster
They're the same

Practice Playground

Time to try out what you just learned! Play with the example code below, experiment by making changes and running the code to deepen your understanding.

Lesson Progress

  • Fix This Code
  • Quick Quiz
  • Practice Playground - run once