🔴 Advanced · Lesson 63

Sorting and Searching in C++

Q: How do I sort a vector in descending order in C++?

Pass a comparator to std::sort: std::sort(v.begin(), v.end(), std::greater<int>()); or use a lambda [](int a, int b) { return a > b; }. Another option is std::sort(v.rbegin(), v.rend());, which sorts the reversed range in ascending order.

Q: What is the difference between lower_bound and upper_bound?

On a sorted range, lower_bound(x) returns an iterator to the first element that is not less than x (≥ x), and upper_bound(x) returns the first element greater than x. The distance between them is the number of elements equal to x.

In this lesson: Sort and search in C++ with std::sort, binary_search, lower_bound and manual algorithms — with output. In Hindi & English.

Why sorting and searching matter

Sorting (arranging data in order) and searching (finding an item) are the two most common operations on data — rank lists, merit lists, finding a roll number, checking if a book is in the library. C++ gives you fast, tested versions in <algorithm>, and exams also ask you to write the classic algorithms by hand. This lesson covers both.

std::sort

C++

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

int main() {
    std::vector<int> marks = {66, 91, 78, 55, 84, 91};

    std::sort(marks.begin(), marks.end());                       // ascending
    for (int m : marks) std::cout << m << " ";
    std::cout << "\n";

    std::sort(marks.begin(), marks.end(), std::greater<int>());  // descending
    for (int m : marks) std::cout << m << " ";
    std::cout << "\n";

    int arr[] = {5, 2, 9, 1};
    std::sort(arr, arr + 4);                                     // plain arrays too
    std::cout << arr[0] << " " << arr[3] << "\n";
    return 0;
}

55 66 78 84 91 91 91 91 84 78 66 55 1 9

std::sort runs in O(n log n) and needs random-access iterators (vector, deque, arrays). For std::list use list.sort().

Sorting objects with a comparator

C++

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

struct Student { std::string name; int marks; };

int main() {
    std::vector<Student> cls = {{"Ravi", 78}, {"Aman", 91}, {"Sara", 78}, {"Priya", 91}};

    // highest marks first; if equal, alphabetical by name
    std::sort(cls.begin(), cls.end(), [](const Student& a, const Student& b) {
        if (a.marks != b.marks) return a.marks > b.marks;
        return a.name < b.name;
    });

    int rank = 1;
    for (const auto& s : cls) std::cout << rank++ << ". " << s.name << " " << s.marks << "\n";
    return 0;
}

1. Aman 91 2. Priya 91 3. Ravi 78 4. Sara 78

The comparator must return true when a should come before b, and must be a strict ordering — never return true for equal elements (>= instead of > can crash sort).

Other sorting functions

Function	Use it when
`std::stable_sort`	Equal elements must keep their original order (e.g. sort by marks but keep roll-number order among ties)
`std::partial_sort(b, b + k, e)`	You only need the top `k` sorted (top 3 rankers)
`std::nth_element`	You need the k-th smallest / the median, not the full order
`std::is_sorted`	Check whether a range is already sorted
`std::reverse`	Reverse a range

Linear search with find / find_if

Works on any data, sorted or not — O(n).

C++

std::vector<int> rolls = {12, 7, 25, 3, 18};
auto it = std::find(rolls.begin(), rolls.end(), 25);
if (it != rolls.end())
    std::cout << "found at index " << (it - rolls.begin()) << "\n";   // 2

auto big = std::find_if(rolls.begin(), rolls.end(), [](int r) { return r > 15; });
std::cout << "first roll > 15: " << *big << "\n";                     // 25

Binary search on sorted data

Binary search looks at the middle element and discards half the range each step — O(log n). The data must be sorted by the same order.

C++

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

int main() {
    std::vector<int> marks = {35, 48, 55, 66, 66, 66, 78, 91};

    std::cout << std::boolalpha
              << "66 present? " << std::binary_search(marks.begin(), marks.end(), 66) << "\n"
              << "70 present? " << std::binary_search(marks.begin(), marks.end(), 70) << "\n";

    auto lo = std::lower_bound(marks.begin(), marks.end(), 66);   // first >= 66
    auto hi = std::upper_bound(marks.begin(), marks.end(), 66);   // first > 66
    std::cout << "66 appears " << (hi - lo) << " times, starting at index "
              << (lo - marks.begin()) << "\n";

    auto pos = std::lower_bound(marks.begin(), marks.end(), 70);
    std::cout << "70 would be inserted at index " << (pos - marks.begin()) << "\n";
    return 0;
}

66 present? true 70 present? false 66 appears 3 times, starting at index 3 70 would be inserted at index 6

Writing the classic algorithms yourself

Bubble sort — O(n²)

C++

void bubbleSort(std::vector<int>& a) {
    for (size_t i = 0; i + 1 < a.size(); i++) {
        bool swapped = false;
        for (size_t j = 0; j + 1 < a.size() - i; j++) {
            if (a[j] > a[j + 1]) {
                std::swap(a[j], a[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;          // already sorted: stop early
    }
}

Binary search — O(log n)

C++

int binarySearch(const std::vector<int>& a, int key) {
    int low = 0, high = static_cast<int>(a.size()) - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;     // avoids overflow of (low + high)
        if (a[mid] == key) return mid;
        if (a[mid] < key)  low = mid + 1;
        else               high = mid - 1;
    }
    return -1;                                // not found
}

For more hand-written sorts see bubble sort, selection and insertion sort and merge sort.

Complexity at a glance

Algorithm	Best	Average	Worst	Stable?
Bubble sort	O(n)	O(n²)	O(n²)	Yes
Selection sort	O(n²)	O(n²)	O(n²)	No
Insertion sort	O(n)	O(n²)	O(n²)	Yes
Merge sort / `stable_sort`	O(n log n)	O(n log n)	O(n log n)	Yes
`std::sort` (introsort)	O(n log n)	O(n log n)	O(n log n)	No
Linear search	O(1)	O(n)	O(n)	—
Binary search	O(1)	O(log n)	O(log n)	—

Common mistakes

Running binary_search or lower_bound on unsorted data — the result is meaningless.
Using <= or >= in a sort comparator — violates strict weak ordering and can crash.
Writing std::sort(v.begin(), v.end() - 1) and missing the last element.
Calculating mid = (low + high) / 2 with huge indices — can overflow; use low + (high - low) / 2.
Using std::sort on a list.

🏋️ Practice

Read the names and marks of 8 students. Print a merit list (marks descending, ties by name). Then ask for a mark and use lower_bound/upper_bound on a sorted copy of the marks to print how many students scored exactly that mark and how many scored more.

Summary

std::sort sorts in O(n log n); pass std::greater or a lambda for custom order.
Use stable_sort when ties must keep their original order; partial_sort for top-k.
find/find_if = linear search on any data.
binary_search, lower_bound, upper_bound = O(log n) on sorted data.
Know bubble sort and binary search by hand for exams.

Frequently Asked Questions

How do I sort a vector in descending order in C++?

Pass a comparator to std::sort: std::sort(v.begin(), v.end(), std::greater<int>()); or use a lambda [](int a, int b) { return a > b; }. Another option is std::sort(v.rbegin(), v.rend());, which sorts the reversed range in ascending order.

Which sorting algorithm does std::sort use?

The standard only requires O(n log n) comparisons. GCC, Clang and MSVC implement it as introsort — a quicksort that switches to heapsort if recursion gets too deep and to insertion sort for small parts. It is not stable; use std::stable_sort when equal elements must keep their original order.

What is the difference between linear search and binary search?

Linear search checks elements one by one and works on any data in O(n) time. Binary search repeatedly halves a sorted range, taking O(log n) time, but the data must already be sorted. For 1,000,000 elements, linear search may need a million checks; binary search needs about 20.

What is the difference between lower_bound and upper_bound?

On a sorted range, lower_bound(x) returns an iterator to the first element that is not less than x (≥ x), and upper_bound(x) returns the first element greater than x. The distance between them is the number of elements equal to x.

← Back to C++ Tutorial

💻 Live Code Editor

This page's programs are ready here — run them, edit them, and learn. No installation needed.

Powered by OneCompiler. The code loads into the editor automatically — press Run to see the output. If the editor does not open, open it in a new tab.