Skip to content

Sorting and Searching — sort, stable_sort, partial_sort, binary_search, lower_bound

DodaTech Updated 2026-06-28 8 min read

In this tutorial, you will learn about Sorting and Searching. We cover key concepts, practical examples, and best practices to help you master this topic.

C++ provides sort (introsort O(n log n)), stable_sort (mergesort), partial_sort (heap selection), and binary search variants (lower_bound, upper_bound, equal_range) for efficiently ordering and searching ranges.

What You'll Learn

You will sort containers with std::sort, preserve relative order of equivalent elements with stable_sort, find the top k elements with partial_sort and nth_element, search sorted ranges with binary_search, lower_bound, upper_bound, and equal_range, and understand performance characteristics of each algorithm.

Why It Matters

Sorting and searching are fundamental to computing. The STL provides optimized implementations that you should never need to write yourself. Understanding which algorithm to use — and whether your data needs to be sorted at all — separates novice from intermediate programmers.

Learning Path

graph LR
    A["36: Algorithms Overview"] --> B["37: Sorting & Searching"]
    B --> C["38: Modifying Algorithms"]
    C --> D["39: Numeric Algorithms"]
    style A fill:#4a90d9,stroke:#2c5f8a,color:#fff
    style B fill:#4a90d9,stroke:#2c5f8a,color:#fff
    style C fill:#4a90d9,stroke:#2c5f8a,color:#fff
    style D fill:#4a90d9,stroke:#2c5f8a,color:#fff

std::sort

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

int main() {
    std::vector<int> v = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    
    // Default: ascending
    std::sort(v.begin(), v.end());
    for (int x : v) std::cout << x << " ";
    std::cout << "\n";  // 1 2 3 4 5 6 7 8 9
    
    // Descending
    std::sort(v.begin(), v.end(), std::greater<int>());
    for (int x : v) std::cout << x << " ";
    std::cout << "\n";  // 9 8 7 6 5 4 3 2 1
    
    // Custom comparator
    std::sort(v.begin(), v.end(), [](int a, int b) {
        return a % 10 < b % 10;  // sort by last digit
    });
    
    // Sorting with structs
    struct Person { std::string name; int age; };
    std::vector<Person> people = {{"Alice", 30}, {"Bob", 25}, {"Charlie", 35}};
    
    std::sort(people.begin(), people.end(),
              [](const Person& a, const Person& b) {
                  return a.age < b.age;
              });
    
    // Complexity: O(n log n) on average
}

sort uses introsort (quicksort + heapsort), O(n log n) worst-case.

std::stable_sort

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

struct Task {
    int priority;
    std::string name;
};

int main() {
    std::vector<Task> tasks = {
        {3, "Low A"}, {1, "High A"}, {3, "Low B"},
        {2, "Mid A"}, {1, "High B"}
    };
    
    // stable_sort preserves relative order of equal elements
    std::stable_sort(tasks.begin(), tasks.end(),
                     [](const Task& a, const Task& b) {
                         return a.priority < b.priority;
                     });
    
    for (const auto& [p, n] : tasks) {
        std::cout << p << ": " << n << "\n";
    }
    // Output:
    // 1: High A
    // 1: High B  (High A appears before High B — order preserved)
    // 2: Mid A
    // 3: Low A
    // 3: Low B  (Low A before Low B — order preserved)
}

stable_sort uses mergesort, O(n log n) with O(n) extra memory. Use it when you need to preserve the original order of equivalent elements.

std::partial_sort

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

int main() {
    std::vector<int> scores = {55, 88, 72, 95, 63, 91, 78, 82, 87};
    
    // Find top 3 scores (not fully sorted)
    std::partial_sort(scores.begin(), scores.begin() + 3, scores.end(),
                      std::greater<int>());
    
    std::cout << "Top 3: ";
    for (int i = 0; i < 3; ++i) {
        std::cout << scores[i] << " ";
    }
    std::cout << "\n";  // 95 91 88
    
    // Rest of array is in arbitrary order
    std::cout << "Rest: ";
    for (size_t i = 3; i < scores.size(); ++i) {
        std::cout << scores[i] << " ";
    }
    std::cout << "\n";
}

Complexity: O(n log k) where k is the number of sorted elements, k = 3 here.

std::nth_element

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

int main() {
    std::vector<int> v = {55, 88, 72, 95, 63, 91, 78, 82, 87};
    
    // Find the median (5th element, index 4)
    auto mid = v.begin() + v.size() / 2;
    std::nth_element(v.begin(), mid, v.end());
    
    std::cout << "Median: " << *mid << "\n";
    // Elements before mid are all <= median
    // Elements after mid are all >= median
    // Neither side is sorted
    
    std::cout << "Left:  ";
    for (auto it = v.begin(); it != mid; ++it) std::cout << *it << " ";
    std::cout << "\nMid:   " << *mid << "\n";
    std::cout << "Right: ";
    for (auto it = mid + 1; it != v.end(); ++it) std::cout << *it << " ";
    std::cout << "\n";
}

nth_element is O(n). Use it when you need the kth smallest/largest element or percentile without full sorting.

Binary Search on Sorted Ranges

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

int main() {
    std::vector<int> v = {1, 3, 5, 7, 9, 11, 13, 15};
    
    // binary_search: returns bool
    bool found = std::binary_search(v.begin(), v.end(), 7);
    std::cout << "7 found: " << found << "\n";  // 1
    
    // lower_bound: first element >= value
    auto low = std::lower_bound(v.begin(), v.end(), 8);
    if (low != v.end()) {
        std::cout << "First >= 8: " << *low << " at index "
                  << (low - v.begin()) << "\n";  // 9 at index 4
    }
    
    // upper_bound: first element > value
    auto up = std::upper_bound(v.begin(), v.end(), 7);
    if (up != v.end()) {
        std::cout << "First > 7: " << *up << "\n";  // 9
    }
    
    // equal_range: pair of lower_bound and upper_bound
    v = {1, 2, 2, 2, 3, 4, 5};
    auto [low2, high2] = std::equal_range(v.begin(), v.end(), 2);
    for (auto it = low2; it != high2; ++it) {
        std::cout << *it << " ";  // 2 2 2
    }
    std::cout << "\n";
    std::cout << "Count of 2: " << (high2 - low2) << "\n";  // 3
}

Comparing Sorting Algorithms

Algorithm Complexity Stable Extra Memory Use Case
sort O(n log n) avg No O(log n) General purpose
stable_sort O(n log n) Yes O(n) Need stability
partial_sort O(n log k) No O(log k) Top-k elements
nth_element O(n) avg No O(1) Median/percentile
sort_heap O(n log n) No O(1) When heap exists

Common Mistakes

Mistake 1: Using sort When Data is Nearly Sorted

// If almost sorted, insertion sort is faster
// Use std::sort (introsort handles this well, but consider std::stable_sort for nearly-sorted data)

Mistake 2: Binary Search on Unsorted Range

std::vector<int> v = {5, 3, 1, 4, 2};
std::binary_search(v.begin(), v.end(), 3);  // undefined behavior

Always sort before binary search.

Mistake 3: Off-by-One with lower_bound/upper_bound

lower_bound(value) returns the first position where value could be inserted to maintain order. upper_bound(value) returns the last position where value could be inserted.

Mistake 4: Using sort When nth_element Would Suffice

Finding a median with sort is O(n log n). Using nth_element is O(n).

Mistake 5: Forgetting That sort is Not Stable

If you need to sort by multiple criteria (e.g., first by age, then by name), either use stable_sort for the secondary criterion first, or use a single comparator that checks both.

Mistake 6: Using sort with Non-Random Access Iterators

std::list<int> lst;
// std::sort(lst.begin(), lst.end());  // Error

Use lst.sort() member function instead.

Practice Questions

  1. What is the difference between sort and stable_sort?
  2. When would you use partial_sort instead of sort?
  3. How do you find the position where to insert a value in a sorted vector?
  4. Which algorithm finds the median in O(n) time?
  5. Write a function that finds all elements with a given value in a sorted vector and returns a range of iterators.

Challenge

Implement a "top-k frequent elements" function: given a vector of integers and k, return the k most frequent elements. Use nth_element or partial_sort with a frequency map.

FAQ

What algorithm does `std::sort` use?

Introsort: begins with quicksort, switches to heapsort when recursion depth exceeds log n, and may switch to insertion sort for small partitions.

Is `std::sort` faster than C's `qsort`?

Usually yes. std::sort uses template-based comparators that can be inlined, while qsort uses function pointers that cannot. Expect 2-3x speedup.

What is the difference between `lower_bound` and `upper_bound`?

lower_bound returns first position >= value. upper_bound returns first position > value. For value 5 in {1,3,5,5,7}: lower = index of first 5, upper = index of 7.

Can I use binary search on non-sequential containers?

No. Binary search requires random access iterators. For std::set, use its find() member function.

What is 'introselect'?

The algorithm used by nth_element in many implementations. It combines quickselect with median-of-medians to guarantee O(n) worst-case performance.

How do I sort descending?

Pass std::greater<T>() as the comparator, or use auto cmp = [](auto a, auto b) { return a > b; }; or simply sort ascending and call std::reverse.

Mini Project

Build a grade report generator:

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <iomanip>

struct Student {
    std::string name;
    double grade;
};

void printReport(std::vector<Student> students) {
    std::cout << "Grade Report\n";
    std::cout << "============\n";
    
    // Sort by grade descending
    std::sort(students.begin(), students.end(),
              [](const Student& a, const Student& b) {
                  return a.grade > b.grade;
              });
    
    for (size_t i = 0; i < students.size(); ++i) {
        std::cout << std::setw(2) << (i + 1) << ". "
                  << std::setw(15) << std::left << students[i].name
                  << std::right << std::setw(5) << students[i].grade;
        
        // Letter grade
        if (students[i].grade >= 90) std::cout << " A";
        else if (students[i].grade >= 80) std::cout << " B";
        else if (students[i].grade >= 70) std::cout << " C";
        else std::cout << " D/F";
        std::cout << "\n";
    }
    
    // Median grade
    auto mid = students.begin() + students.size() / 2;
    std::nth_element(students.begin(), mid, students.end(),
                     [](const Student& a, const Student& b) {
                         return a.grade < b.grade;
                     });
    std::cout << "\nMedian grade: " << mid->grade << "\n";
    
    // Top 25% threshold
    auto top = students.begin() + students.size() / 4;
    std::nth_element(students.begin(), top, students.end(),
                     [](const Student& a, const Student& b) {
                         return a.grade > b.grade;
                     });
    std::cout << "Top 25% threshold: " << top->grade << "\n";
}

int main() {
    std::vector<Student> class1 = {
        {"Alice", 95}, {"Bob", 82}, {"Charlie", 78},
        {"David", 91}, {"Eve", 67}, {"Frank", 88},
        {"Grace", 73}, {"Hank", 59}, {"Ivy", 85}
    };
    
    printReport(class1);
}

What's Next

Sorting and searching are core algorithm categories. The next lesson covers modifying algorithms: copy, move, transform, replace, and the erase-remove idiom.

← Previous Algorithms Overview — Categories, Iterator Requirements, Ranges Next → Modifying Algorithms — copy, move, transform, replace, Erase-Remove Idiom

Built by the developers of DodaTech

Doda Browser, DodaZIP & Durga Antivirus Pro

Home Browse Cpp