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.