Efficient algorithm to merge n successive sorted arrays in place

Question

I am developing an in-place sorting algorithm that leaves the array into a state where it is basically a succession of sorted subsequences of any size (most are bigger than log2(size(array))); then it merges the said subsequences in place. Once the described state has been reached, the algorithm in its current form simply merges the first two subsequences, then merges the result with the following subsequence, etc... Note that at the time of merging, we know where the sorted subsequences begin, we don't have to find them again.

While it works fine, I guess that this merging scheme is suboptimal and I believe that it should be possible to use a smarter merging scheme. The best algorithm I could think of would be an algorithm that looks for the smallest successive sorted subsequences and merges them, then repeats until everything has been merged. The idea is that merging smaller sequences first is cheaper, so we should merge the biggest ones only in the end.

Is there a more efficient algorithm to merge n successive subsequences in place?

---

As requested, let's imagine that we want to sort the following array:

10 11 12 13 14 9 8 7 6 5 0 1 2 3 4

My algorithm will do things that are totally irrelevant for the question, but leave the array in the following state:

10 11 12 13 14 0 5 6 7 8 9 1 2 3 4
^              ^           ^

The carets show where big enough sorted subsequences in the array begin; in the actual code, they correspond to iterators, or indices depending on the abstraction you use. The next step is to merge these subsequences together to sort the array (note that all of them are bigger than log2(size(array)) if that matters, but they might have different sizes). To merge the different parts of this array, the smartest move is apparently to merge the last subsequence with the middle one in place, leaving the array in the following state:

10 11 12 13 14 0 1 2 3 4 5 6 7 8 9
^              ^

...then two merge the two remaining subsequences in place so that the array is actually sorted. As I said, there can be up to log2(size(array)) such subsequences before the in-place merge step.

---

My current solution for the merging step involves a bit of indirection: iterators pointed by carets are stored in a list, then I create a min heap where every element is one of the list iterators and the comparison function associates to every iterator the distance between its neighbours. When two subsequences are merged, I pop a value from the heap and remove the corresponding iterators from the list. Here is basically what my C++ algorithm does:

template<typename Iterator, typename Compare=std::less<>>
auto sort(Iterator first, Iterator last, Compare compare={})
    -> void
{
    // Code irrelevant to the question here
    // ...
    //

    // Multi-way merge starts here

    std::list<Iterator> separators = { first, /* beginning of ordered subsequences */, last };
    std::vector<typename std::list<Iterator>::iterator> heap;
    for (auto it = std::next(separators.begin()) ; it != std::prev(separators.end()) ; ++it)
    {
        heap.push_back(it);
    }
    auto cmp = [&](auto a, auto b) { return std::distance(*std::prev(a), *std::next(a)) < std::distance(*std::prev(b), *std::next(b)); };
    std::make_heap(heap.begin(), heap.end(), cmp);

    while (not heap.empty())
    {
        std::pop_heap(heap.begin(), heap.end(), cmp);
        typename std::list<Iterator>::iterator it = heap.back();
        std::inplace_merge(*std::prev(it), *it, *std::next(it), compare);
        separators.erase(it);
        heap.pop_back();
    }
}

I wrote the algorithm in C++ because I find it easier to reason about iterators, but a general algorithmic answer is welcome.

Answer 1

If you repeatedly merge the 2 first sequences you will get a runtime that is much worse than merge sort as you compare the first elements far too many times (n log(n)^2???) if you merge the 2 (or more) smallest (adjacent) sequences each time you should approach merge sorts efficiency.

Finding the smallest adjacent sequences might be done by building a tree with roughly half the sequence in each branch recursively and then merging the lowest branches first.

---- Edit

First version:
Essential a mergesort where the separators are the implicit partition of the mergesort algorithm.

Order separators according to their index in the array

MergeIt(first, last) {
    if (only one or zero separator)
       return first;

    split = separator containing the middle separator (first, last)

    return inplace_merge(MergeIt(first, split), MergeIt(split, end));
}

This ensures that you only do the minimum number of merges, but not the minimum number of compares as larger sequences might be merge with the current minimum sequence.

Version two:
Still basically a mergesort where we now take into consideration the length of the sequences.

Order separators according to their index in the array

MergeIt(first, last) {
    if (only one or zero separator)
       return first;

    split = separator containing the middle element of array(first, last) // not the middle separator

    return inplace_merge(MergeIt(first, split), MergeIt(split, end));
}

The split insures that the smaller sequences merge first as the larger stop higher up in the call tree. This still does not insure the least number of compares as there still is the chance that larger sequences are merge with the current minimum length, though this is still better than version one as the large sequences here are smaller.

Version three:
Merge the adjacent sequences which span the least number of elements

Make heap of pairs of adjacent sequences, sort after minimum length of the pairs, for each sequence only add the shortest of its prev and next.
// each sequence will appear max twice except the first and last.

while (heap.size() > 1) {
    min = heap.pop

    remove the possible other occurrence of min.first and min.second

    sequence = inplace_merge(min.first, min.second)

    insert the minimum of pair(prev(sequence), sequence) and pair(sequence, next(sequence)) in heap.
}

The overhead might make this slower than the second version but the compares in made by inplace_merge should now be the minimum.

Answer 2

I would just do an in place quick sort and write a generic wrapper for your arrays so they can be viewed as one big array.