STL Vector Algorithms: sort, reverse, and lower_bound Complexity

Hello! Last time, you worked with vector boundaries: begin() marks the first element, while end() marks the position just past the last. Those same boundaries let you hand a range to a standard algorithm without writing its loop yourself.

In this lesson, you will use std::sort, std::reverse, and std::lower_bound on vectors. The interview skill is not only remembering their names: it is knowing what range each call affects, what ordering a search requires, and how much work the call performs.

Sort: establish an order

std::sort(first, last) rearranges the elements in the half-open range [first, last). For a vector of integers, the default result is ascending order. The common whole-vector call is:

std::sort(values.begin(), values.end());

Watch the sorting portion of Complete C++ STL in 1 Video | Time Complexity and Notes from take U forward. Concentrate on sorting a vector in ascending order and on the brief discussion of reverse. The custom-comparator examples preview a later lesson; you do not need to write one today.

Here is the essential form in a complete C++17 program:

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> values{7, 4, 2, 4, 9};

    std::sort(values.begin(), values.end());
    // values is now {2, 4, 4, 7, 9}
}

The algorithms in this lesson are declared in <algorithm>. sort changes the vector itself; it does not return a sorted vector. It leaves the number of elements unchanged, but their positions may change. If two elements compare equal, std::sort does not promise to preserve their original relative order—a distinction that will matter when you later sort records.

You can also sort a subrange. For example, with {8, 5, 3, 7, 1}, the call std::sort(values.begin() + 1, values.begin() + 4) sorts only the three elements at indices 1, 2, and 3. The result is {8, 3, 5, 7, 1}, not a sorted vector. As in the previous lesson, the second iterator is excluded, and any iterator formed by adding an index must remain within the vector’s valid boundaries.

For $n$ elements, std::sort performs $O(n\log n)$ comparisons. In ordinary interview analysis with integers and constant-time comparisons, state its time complexity as $O(n\log n)$. Sorting an already sorted vector is not a reason to describe a general std::sort call as $O(n)$.

Reverse: change positions, not values

std::reverse(first, last) swaps elements from opposite ends of the specified range. It does not compare values or determine whether they are sorted.

Read the short definition and complexity line in cppreference’s std::reverse. They make the difference between “reversing” and “sorting in descending order” precise.

For example:

std::vector<int> values{2, 4, 4, 7, 9};

std::reverse(values.begin(), values.end());
// values is now {9, 7, 4, 4, 2}

Because this vector started in ascending order, reversing it happened to produce descending order. Reverse {4, 9, 2}, however, and you get {2, 9, 4}—still unsorted. Do not use reverse as a substitute for sort on arbitrary input.

Reversing $n$ elements takes exactly $\lfloor n/2\rfloor$ swaps, so its time complexity for integer vectors is $O(n)$. An empty vector and a one-element vector require no swaps. Like sort, it works on the specified range in the existing vector rather than producing a new vector.

There is a useful connection to iterator safety here. Sorting and reversing do not change the vector’s size, but they can change the value at a position. If you saved an index because it held a particular value, that assumption may be false after either operation.

Lower bound: find the first place a value could go

Once a vector is sorted in ascending order, std::lower_bound(first, last, target) finds the first element that is not less than target. For integers, read that as “the first element greater than or equal to the target.” It returns an iterator, not an index or a Boolean.

Watch the lower_bound portion of STL Algorithms 2: std::binary_search, std::lower_bound & std::upper_bound from code_report. Pay particular attention to its examples with duplicates, a missing value between existing values, and a value beyond the end.

Consider {2, 4, 4, 7, 9}:

• For target 4, lower_bound points to the first 4, at index 1.
• For target 5, it points to 7, at index 3. This is where 5 could be inserted while retaining ascending order.
• For target 12, it returns end(): no element is at least 12.
• For target 1, it returns begin().

The important distinction is that a returned element need not equal the target. Here is a complete example that sorts an initially unsorted vector, searches it, and then reverses it:

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

int main() {
    std::vector<int> values{7, 4, 2, 4, 9};
    std::sort(values.begin(), values.end());
    // {2, 4, 4, 7, 9}

    const int target = 5;
    auto it = std::lower_bound(values.begin(), values.end(), target);

    if (it != values.end()) {
        auto index = it - values.begin();
        std::cout << "First value at least " << target
                  << " is " << *it << " at index " << index << '\n';
        // Prints: First value at least 5 is 7 at index 3
    } else {
        std::cout << "No value is at least " << target << '\n';
    }

    std::reverse(values.begin(), values.end());
    // {9, 7, 4, 4, 2}
}

The it != values.end() check must come before *it: as you saw previously, end() is not an element. Subtracting values.begin() converts a vector iterator into its zero-based index. If your task asks whether the target is present, check both that the iterator is not end() and that *it == target.

lower_bound relies on the range being ordered appropriately for its comparison. An ascending integer vector is the straightforward case. After the final reverse above, you should not call the default lower_bound on the whole now-descending vector and expect the same behavior. Later lessons will develop binary search and alternative ordering rules; for now, sort ascending before using the default call.

On a vector, lower_bound takes $O(\log n)$ time: it can repeatedly rule out a substantial portion of the remaining search range. That logarithmic time statement matters specifically here because vector iterators allow direct access to positions. By contrast, sorting the vector first costs $O(n\log n)$; a single search does not make the combined operation $O(\log n)$.

Choosing and costing the call

The choice depends on the state you need afterward. If a problem gives an unsorted vector and asks for its ordered contents, use sort. If it asks you to flip an existing sequence, use reverse. If it asks for a position in an already sorted vector, lower_bound avoids scanning each element. When sorting is necessary first, include that cost in your explanation.

Takeaways

All three algorithms use the same half-open iterator range you practiced last time. sort orders its range in $O(n\log n)$ time; reverse flips it in $O(n)$; and lower_bound finds the first qualifying position in $O(\log n)$ time on an appropriately sorted vector. Always check a lower_bound result against end() before dereferencing it, and check equality separately if you need an exact match.

Next, you will look at how to pass data into interview functions using const references, values, and range-based loops—choices that affect both clarity and unnecessary copying.