7

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.

3
  • In-place merging is a well-studied problem. See, for example, stackoverflow.com/questions/2571049/…. In particular the first answer, in which the paper is quoted as saying that "due to the constant factors involved the algorithm is predominantly of theoretical interest." Still, it might give you some insight into how to do your in-place merging. Jan 4, 2016 at 19:54
  • Did you read this question? Moreover: your question would be much better asked in something like ComputerScience.SE, or StackOverflow if you are looking for an implementation.
    – Bakuriu
    Mar 1, 2016 at 21:25
  • @Bakuriu I'll look at the question (I don't remember seeing it). Asking this kind of question is hard: SO is for "specific" problems while this one is generic enough to be of interest to every programmer (not about a specific programming language despite the C++ example), but it still doesn't feel CS enough for a CS site: it isn't about proof, complexity or anything, just about which known algorithm would be the best for a specific case. Sometimes the number of sites makes i hard to know where to post :/
    – Morwenn
    Mar 1, 2016 at 21:55

2 Answers 2

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.

4
  • Is the tree structure you have in mind some sort of heap?
    – Giorgio
    Dec 31, 2015 at 12:39
  • @Giorgio, I was thinking an ordered tree after the position of the segments in the array, so that if you make an in-order traversal of the tree you get the original array.
    – Surt
    Dec 31, 2015 at 13:42
  • You don't need to actually build the tree. Find the subarray boundary that is closest to the middle, cut the array (virtually) in two, merge the 2 sides using the same method recursively and then merge the 2 halves.
    – Florian F
    Jan 1, 2016 at 1:15
  • @FlorianF, that might actually be easier and it further has the advantage that you don't need to build another structure.
    – Surt
    Jan 1, 2016 at 10:31
-3

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.

2
  • 1
    Could you explain what you mean in more detail? Dec 31, 2015 at 0:05
  • It looks like a case of confusion: it seems that they thought that I was trying to merge n sorted arrays into another big array while those « n arrays » are already a single big array that's only waiting for a big in-place merge operation.
    – Morwenn
    Dec 31, 2015 at 12:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.