C++ Basics: Merge Two Sorted Halves Inside One Vector
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 1Run 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-demoObserved output:
1:left
2:right
3:left
3:right
4:right
5:leftRead 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_directoryIf the directory is not empty, inspect its remaining contents before removing anything else.
Acknowledgements
This post was created with assistance from AI.