Skip to content
Tutorials Center
My learning

Topics

Lesson 160 of 171 · Data Structures and Algorithms

Searching and Sorting Algorithms

Implement linear and binary search plus bubble, selection, insertion, merge, quick and heap sort in C++, with traces, Big-O analysis and timings against std::sort.

Searching and sorting are the two most studied problems in computer science, and for good reason: almost every program does both. A search engine sorts results by relevance, a database finds rows by key, a game sorts sprites by depth before drawing them. The standard library hands you std::sort and std::ranges::lower_bound, which are excellent, but knowing how they work tells you when they're fast, when they're slow, what "stable" means, and why sorting first can turn an impossibly slow program into an instant one.

In this lesson you'll implement linear and binary search, then six classic sorting algorithms: bubble, selection and insertion sort (simple, O(n²)), and merge, quick and heap sort (clever, O(n log n)). Each one comes with a step-by-step trace so you can watch it work. At the end you'll race all of them against std::sort, counting comparisons and timing them with <chrono>.

You should know vectors, function templates and lambdas. The library side of this topic is covered in Algorithms: Searching, Sorting and Counting; recursion helps for merge sort and quicksort.

Measuring algorithms: Big-O

To compare algorithms independently of the computer, count the work they do as a function of the input size n, and keep only the fastest-growing term. That's Big-O notation:

Growth Name n = 1,000 n = 1,000,000 Example
O(1) constant 1 1 indexing a vector
O(log n) logarithmic ~10 ~20 binary search
O(n) linear 1,000 1,000,000 linear search
O(n log n) linearithmic ~10,000 ~20,000,000 merge sort, std::sort
O(n²) quadratic 1,000,000 1,000,000,000,000 bubble sort

The last column is the one that matters. At a million elements, an O(n log n) sort does about 20 million steps, a fraction of a second. An O(n²) sort does a trillion, which would take many minutes. No amount of micro-optimization rescues a quadratic algorithm on big inputs; choosing the right algorithm does.

Two refinements matter in practice. Best, average and worst case can differ: insertion sort is O(n) on already-sorted input but O(n²) on reversed input. And constant factors still count among algorithms of the same class: an O(n log n) sort that streams through memory beats one that jumps around.

Linear search checks each element in turn until it finds the target or runs out. It works on any data, sorted or not, and costs O(n): on average it looks at half the elements when the target is present, and all of them when it's absent.

C++
template <typename T>
std::optional<std::size_t> linear_search(const std::vector<T>& items, const T& target) {
    for (std::size_t i = 0; i < items.size(); ++i) {
        if (items[i] == target) {
            return i;
        }
    }
    return std::nullopt;
}

Returning std::optional<std::size_t> makes "not found" impossible to confuse with a valid index, unlike the old habit of returning -1. The standard equivalent is std::ranges::find, which returns an iterator. For small collections (a few dozen elements) linear search is often the fastest option there is, because it's simple and cache-friendly.

If the data is sorted, you can do much better. Binary search compares the target with the middle element. If they're equal, you're done. If the target is smaller, it can only be in the left half; if larger, only in the right half. Each step discards half of the remaining range, so a million elements need at most 20 comparisons and a billion need at most 30.

The details are where binary search bugs live, so it pays to be precise. This version uses a half-open range [lo, hi): lo is the first candidate and hi is one past the last. The range is empty when lo == hi.

C++ Binary search, step by step

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Searching for 20 shows how a failed search ends: the range shrinks until lo == hi, and that position (index 8, where 23 sits) is exactly where 20 would have to be inserted to keep the vector sorted.

Three classic bugs to avoid:

  • Midpoint overflow. (lo + hi) / 2 can overflow when lo + hi exceeds the type's maximum, which bit real-world libraries for years. lo + (hi - lo) / 2 can't overflow. C++20 also offers std::midpoint(lo, hi) in <numeric>.
  • Off-by-one loops. Mixing the half-open style (hi = size, while (lo < hi), hi = mid) with the closed style (hi = size - 1, while (lo <= hi), hi = mid - 1) produces infinite loops or skipped elements. Pick one style and stick to it. With unsigned indexes, the closed style also has to guard against mid - 1 wrapping around below zero, which is one more reason to prefer half-open ranges.
  • Unsorted input. Binary search on unsorted data doesn't fail loudly; it just returns wrong answers.

lower_bound and binary search on the answer

Often you don't want "is it there?" but "where is the first element ≥ x?". That's lower bound, and the second loop in the program above already computes it: it never stops early, and when it ends, lo is the first position whose value is not less than the target. std::ranges::lower_bound does exactly this, and upper_bound finds the first element greater than the target. The count of elements equal to x is upper_bound - lower_bound.

The same idea works on any monotonic yes/no question, not just arrays. If a condition is false up to some point and true afterwards, binary search finds the switching point. This technique, often called "binary search on the answer", solves problems like integer square roots, the minimum speed to finish a job on time, or the smallest buffer that fits a workload.

C++ lower_bound by hand and binary search on the answer

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

The simple sorts: bubble, selection and insertion

The three simple sorts are all O(n²) on average, but they're worth knowing: they're short, they sort in place with O(1) extra memory, and insertion sort is genuinely the fastest algorithm for small or nearly sorted arrays.

All implementations in this lesson take a std::vector<T>& and an optional comparison less, defaulting to std::ranges::less (which calls <). Passing a different comparator sorts in a different order, and later we'll pass one that counts comparisons.

  • Bubble sort walks through the array, swapping neighbors that are out of order. After the first pass, the largest element has "bubbled" to the end; after the second, the second largest; and so on. If a pass makes no swaps, the array is sorted and it can stop early, so it's O(n) on sorted input.
  • Selection sort finds the smallest remaining element and swaps it into the next position. It always does about n²/2 comparisons, even on sorted input, but at most n − 1 swaps, which matters only when moving elements is very expensive.
  • Insertion sort grows a sorted prefix one element at a time: it takes the next element and shifts larger ones right until it finds the element's place, the way you'd sort a hand of cards. On nearly sorted data, each element moves only a little, so it approaches O(n).
C++ Bubble, selection and insertion sort, pass by pass

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Read the bubble sort trace: after each pass, the largest remaining value has reached the end (9, then 6, then 5…), and the fourth pass makes no swaps, so it stops. Insertion sort's trace shows the sorted prefix growing by one element per step. Notice that insertion sort moves elements instead of swapping them: one move per shift instead of three for a swap.

Merge sort: divide and conquer

Merge sort splits the array in half, sorts each half recursively, then merges the two sorted halves into one. Merging is the clever part: compare the front elements of both halves, take the smaller one, repeat. That's linear time, because each element is taken once.

Why O(n log n)? Splitting in half repeatedly gives log₂ n levels of recursion, and each level merges a total of n elements. So the cost is n per level times log n levels, in the best, average and worst case. The price is a buffer of n elements for merging, so merge sort uses O(n) extra memory.

Merge sort is also stable: equal elements keep their original relative order. The merge guarantees it by taking from the left half when the two front elements are equal.

C++ Merge sort with a recursion trace

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

The indentation shows the recursion depth. Each split line is a call dividing its range, and each merged line is that same call finishing, with its whole range now sorted. Notice that the buffer is allocated once in the outer function and shared by every call; allocating a fresh vector at every level is a common mistake that makes merge sort several times slower.

Merge sort shines when stability is required, when the worst case must be guaranteed, and for data that doesn't fit in memory: external sorting sorts chunks that fit, writes them to disk, then merges the sorted files. It also works naturally on linked lists, where merging needs no buffer at all (std::list::sort is a merge sort). std::stable_sort is a tuned merge sort too.

Quicksort: partitioning around a pivot

Quicksort also divides and conquers, but does its work before recursing. It picks a pivot element and partitions the array: everything smaller than the pivot moves to the left, everything else to the right, and the pivot lands in its final sorted position. Then it sorts the two sides recursively. No merge step is needed and no buffer: quicksort sorts in place.

This version uses the Lomuto partition: park the pivot at the end, sweep a store index from the left, and swap each element smaller than the pivot to the store position. Finally swap the pivot into store.

C++ Quicksort with partition traces

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Each trace line shows one partition: the left part (all smaller than the pivot), the pivot in brackets at its final index, and the right part. The left and right parts are not sorted yet, but they never need to exchange elements again.

Quicksort's speed depends entirely on the pivot:

  • With good pivots that split the range roughly in half, there are about log₂ n levels and the average cost is O(n log n). Its inner loop is so tight that, in practice, quicksort is usually the fastest comparison sort on arrays.
  • With bad pivots, for example always picking the first element of already-sorted data, one side is empty every time, and the cost becomes O(n²). Choosing the middle element, as here, fixes sorted and reversed inputs; picking the median of three elements or a random element makes bad cases rarer still.
  • Many equal elements hurt the Lomuto partition: when all values are equal, every element goes to the right side, and the sort turns quadratic. The benchmark below shows this. Three-way partitioning ("less, equal, greater") solves it.

Recursing into the smaller side and looping on the larger one guarantees a recursion depth of at most log₂ n, even in the worst case, so quicksort can't overflow the stack.

Quicksort isn't stable: the long-distance swaps reorder equal elements.

Heap sort

Heap sort uses a binary max-heap: an array viewed as a complete binary tree where the children of index i are at 2i + 1 and 2i + 2, and every parent is at least as large as its children. So the largest element is always at index 0. The same structure powers std::priority_queue (see Container Adapters).

The algorithm has two phases:

  1. Build the heap: call sift_down on every parent, from the last one back to the root. sift_down swaps a node with its larger child until it's larger than both. Building the whole heap this way takes only O(n).
  2. Extract repeatedly: swap the root (the maximum) with the last element of the heap, shrink the heap by one, and sift the new root down. The maximum is now in its final position at the end. Repeat n − 1 times, at O(log n) each.
C++ Heap sort: build a heap, then extract the maximum

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

The max-heap [10, 5, 8, 4, 1, 3, 7] reads as a tree with 10 at the root, 5 and 8 as its children, then 4 and 1 under 5, and 3 and 7 under 8. Every parent beats its children, but the array as a whole isn't sorted; a heap is only "sorted enough" to find the maximum instantly.

The loop for (std::size_t i = n / 2; i-- > 0;) counts down to zero with an unsigned index: the condition tests i and then decrements it, so the body sees n/2 − 1, …, 0 and the loop never wraps below zero.

Heap sort is O(n log n) in every case and needs O(1) extra memory, a combination neither merge sort nor quicksort offers. In practice it's slower than quicksort because sifting jumps across the array and defeats the cache, and it isn't stable. Its real job today is as the safety net inside std::sort.

How std::sort really works

std::sort in GCC, Clang and MSVC is an introsort (introspective sort), a hybrid that combines the strengths of the algorithms above:

  1. It runs quicksort with median-of-three pivots, because that's fastest on average.
  2. It tracks the recursion depth. If it exceeds about 2·log₂ n, the pivots are going badly, so it switches to heap sort for that range. This guarantees O(n log n) in the worst case, which the standard has required since C++11.
  3. Ranges shorter than about 16 elements are left alone and finished with one pass of insertion sort at the end, since insertion sort beats everything on tiny inputs.

std::stable_sort uses merge sort (with a buffer when it can get one), and std::partial_sort uses a heap. So you've now implemented the building blocks of the whole standard library sorting toolkit.

Also note that no comparison sort can beat O(n log n) in the worst case: there are n! possible orders of n elements, and each comparison gives one bit of information, so at least log₂(n!) ≈ n log₂ n comparisons are needed. Algorithms like counting sort and radix sort go faster, O(n + k), by not comparing: they use the values themselves as indexes, which works for small integer keys.

The race: counting comparisons and timing

Now let's run everything on the same data. The comparator counts how many times it's called, which is deterministic, and std::chrono::steady_clock measures wall time (see Dates, Times and Durations). The quadratic sorts get 3,000 elements; the fast ones get 200,000. Each result is checked with std::ranges::is_sorted.

C++ Racing six sorts against std::sort

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Your exact timings will vary from run to run, but the comparison counts are fixed by the seed, and the shape of the results is always the same:

  • On 3,000 random elements, the three quadratic sorts make millions of comparisons (bubble and selection about 4.5 million, insertion about half that), while merge sort and std::sort need only about 31,000 and 41,000.
  • On 200,000 elements, merge, quick, heap and std::sort all stay in the low millions of comparisons and finish in milliseconds. A quadratic sort would need about 20 billion comparisons for the same input.
  • On nearly sorted data, insertion sort beats everything, because each element only moves a short distance. That's why introsort finishes with insertion sort.
  • On 10,000 equal values, our Lomuto quicksort collapses to about 50 million comparisons, the quadratic worst case, while std::sort, which handles equal keys gracefully, needs a tiny fraction of that.

The comparisons are counted through a lambda that captures comparisons by reference. Passing comparators as template parameters, rather than as function pointers or std::function, lets the compiler inline them, which is one reason std::sort is faster than C's qsort.

Choosing an algorithm

Algorithm Best Average Worst Extra memory Stable
Linear search O(1) O(n) O(n) O(1) —
Binary search (sorted input) O(1) O(log n) O(log n) O(1) —
Bubble sort O(n) O(n²) O(n²) O(1) yes
Selection sort O(n²) O(n²) O(n²) O(1) no
Insertion sort O(n) O(n²) O(n²) O(1) yes
Merge sort O(n log n) O(n log n) O(n log n) O(n) yes
Quicksort O(n log n) O(n log n) O(n²) O(log n) stack no
Heap sort O(n log n) O(n log n) O(n log n) O(1) no
std::sort (introsort) O(n log n) O(n log n) O(n log n) O(log n) no

In real C++ code the decision is short:

  • Sort with std::ranges::sort; use std::ranges::stable_sort when equal elements must keep their order (for example, sorting by a second key after sorting by a first).
  • Use std::ranges::partial_sort or std::ranges::nth_element when you only need the top k or the median.
  • Search sorted data with std::ranges::lower_bound / binary_search; for unsorted data searched many times, sort once (O(n log n)) and then binary search (O(log n) each), or use a hash set.

Stability is easy to see with records. Sorting people by age with a stable sort keeps people of the same age in their previous order:

C++ Stable versus unstable sorting

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

With stable_sort, the 25-year-olds come out as Bo, Di, Flo and the 30-year-olds as Ana, Cy, Ed: still alphabetical within each age. Selection sort is different: its second swap sends Ana from index 1 to index 3, jumping over Cy, and its third sends Cy to the very end, jumping over Ed. The 30-year-olds come out as Ana, Ed, Cy, and the alphabetical order is lost.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. Binary search on a sorted vector of 1,000,000 elements needs at most about how many comparisons?

    Each comparison halves the range, and 2^20 is about a million, so about 20 steps suffice.
  2. 2. Why is lo + (hi - lo) / 2 preferred over (lo + hi) / 2 for the midpoint?

    lo + hi can exceed the type's maximum value. hi - lo never does, so the rewritten form gives the same midpoint without overflow. std::midpoint does the same job.
  3. 3. Which sort is the best choice for an array that is already almost sorted, with only a handful of elements out of place?

    Insertion sort only shifts each element as far as it is out of place, so nearly sorted input costs close to O(n). Selection sort is always O(n²), and first-element quicksort degrades to O(n²) on sorted data.
  4. 4. What guarantees that std::sort is O(n log n) even in the worst case?

    Introsort watches the recursion depth. When quicksort's pivots go badly, it falls back to heap sort, which is O(n log n) in every case.
  5. 5. Merge sort takes from the LEFT half when two front elements are equal. What property does that give it?

    Elements of the left half came earlier in the input, so preferring them on ties keeps equal elements in their original relative order.

Summary

  • Big-O describes how work grows with input size; at large n, O(n log n) versus O(n²) is the difference between milliseconds and hours.
  • Linear search works on anything in O(n). Binary search needs sorted data and runs in O(log n); use half-open ranges and lo + (hi - lo) / 2, and remember it also finds insertion points (lower bound) and answers to monotonic questions.
  • Bubble, selection and insertion sort are O(n²); insertion sort is the champion for tiny or nearly sorted arrays.
  • Merge sort is O(n log n) always and stable, at the cost of an O(n) buffer. Quicksort is fastest on average but O(n²) with bad pivots or many duplicates. Heap sort is O(n log n) always with O(1) memory, but cache-unfriendly.
  • std::sort is an introsort (quicksort + heap sort fallback + insertion sort finish). Use std::ranges::sort and stable_sort in real code, and measure with <chrono> and comparison counts.

Next: Graphs, Recursion and Backtracking, where you'll represent graphs with adjacency lists, explore them with BFS and DFS, find shortest paths with Dijkstra and solve puzzles by backtracking.