C++ Basics: Merge Two Sorted Lists Without Dropping Duplicates

Use std::merge to combine sorted inputs while retaining every occurrence.

Prepare a scratch directory

Tested on Linux x86_64 with GCC 14.2.0. Install a C++20-capable compiler and standard-library development headers, with g++ on PATH. You also need 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 merge-sorted-streams-demo.cpp:

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

int main()
{
    const std::vector<int> morning{1, 3, 3};
    const std::vector<int> afternoon{2, 3, 4};
    std::vector<int> all;
    all.reserve(morning.size() + afternoon.size());
    std::merge(morning.begin(), morning.end(), afternoon.begin(), afternoon.end(), std::back_inserter(all));
    std::cout << "Merged:";
    for (int value : all) std::cout << ' ' << value;
    std::cout << "\nCount: " << all.size() << '\n';
}

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

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

Observed output:

Merged: 1 2 3 3 3 4
Count: 6

Read the result

All six values appear in sorted order. The three occurrences of 3 remain because merge preserves every input element. It is also stable: equivalent elements from the first input precede equivalent elements from the second, while each input retains its own order.

Apply it carefully

Both inputs must already be sorted using the same comparison. The destination must not overlap them; use inplace_merge for adjacent sorted runs in one range. reserve here is an allocation hint, while back_inserter creates output elements. For untrusted sizes, consider capacity limits and allocation failure before reserving a combined buffer.

The C++ working draft describes the relevant rules. This example builds in C++20 mode; the current working draft also documents later additions.

Clean up

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

rm -- merge-sorted-streams-demo.cpp merge-sorted-streams-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.