Daily bit(e) of C++ | Merging sorted lists
Daily bit(e) of C++ #16, Common interview question: Merging sorted lists with a C++ twist
Today, we will look at another common interview question — Merging sorted lists.
However, since this is C++, we will make a slight twist and add the requirement of avoiding unnecessary copies.
Problem formulation
Given sorted lists as std::vector<std::forward_list<>>, produce a merged sorted std::forward_list<>.
Your implementation should take care of big-O complexity and avoid unnecessary copies.
To that effect, the input is given by value and can be modified.
Before you read the solution, try to solve it yourself: https://compiler-explorer.com/z/5raraWG5f.
Solution
We have two options for approaching this problem.
We can either repeatedly pick the list with the smallest leading element, leading to n (number of elements) repetitions of log(k) (picking the smallest element).
Or we can repeatedly merge pairs of lists, leading to log(k) (since we divide the number of lists by two in each iteration) repetitions of n operations during the merge.
There are several places where we need to be careful with copies. First, when moving lists around, we need to swap or move them.
Second, we will need an ordered data structure for the first solution. Whenever we extract the first element from the list, we need to extract the list from the data structure and only then modify it. This is a potential place where copies can be introduced, so we need to be careful.
Solution A (repeatedly pick the list with the lowest leading element):
Solution B (repeatedly merge pairs of lists):
