Skip to content
C++ Basics: Merge Two Sorted Halves Inside One Vector

C++ Basics: Merge Two Sorted Halves Inside One Vector

November 8, 2026

Use inplace_merge when two adjacent parts of one buffer are already sorted by the same ordering.

Prepare a scratch directory

Tested on Linux x86_64 with GCC 14.2.0. You need a C++20-capable compiler and standard-library development headers, with g++ on PATH, plus Bash, a text editor, and the mktemp, rm, and rmdir utilities. No third-party library is required.

Keep the same terminal open. Stop if setup fails, before saving the source:

start_directory="$PWD"
work_directory="$(mktemp -d)" || exit 1
cd -- "$work_directory" || exit 1

Run the example

Save this as inplace-merge-sorted-halves-demo.cpp:

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

struct Record { int key; std::string source; };

int main()
{
    std::vector<Record> records{{1, "left"}, {3, "left"}, {5, "left"},
                                {2, "right"}, {3, "right"}, {4, "right"}};
    auto by_key = [](const Record& a, const Record& b) { return a.key < b.key; };
    std::inplace_merge(records.begin(), records.begin() + 3, records.end(), by_key);
    for (const auto& record : records) {
        std::cout << record.key << ':' << record.source << '\n';
    }
}

Compile and run it. The program runs only after compilation succeeds:

g++ -std=c++20 -Wall -Wextra -Werror -pedantic inplace-merge-sorted-halves-demo.cpp -o inplace-merge-sorted-halves-demo &&
./inplace-merge-sorted-halves-demo

Observed output:

1:left
2:right
3:left
3:right
4:right
5:left

Read the result

The two sorted halves become one sorted vector. The equal key 3 from the left half stays before the equal key from the right half because the merge is stable.

Apply it carefully

Both halves must already be sorted by the same strict weak ordering. The middle iterator marks the boundary, not an extra output buffer. The algorithm may allocate temporary storage despite its name; in-place refers to the destination range. If neither half is sorted, sort first or use a full sort instead.

The C++ working draft describes the relevant rules. This example uses C++20; the current working draft also includes later additions.

Clean up

Remove only the source and executable created here, then return to the starting directory:

rm -- inplace-merge-sorted-halves-demo.cpp inplace-merge-sorted-halves-demo
cd -- "$start_directory" || exit 1
rmdir -- "$work_directory"
unset start_directory work_directory

If the directory is not empty, inspect its remaining contents before removing anything else.

Acknowledgements

This post was created with assistance from AI.

Last updated on