Run-aware merge sort

Question

The concept is very, very simple: let's do merging run by run (a run is a range without decrement).

template <class RandomIt>
void RunAwareMergeSort(RandomIt first, RandomIt last) {
    RandomIt m_first(first); // the begin of first run of merge
    RandomIt i(first); // the locater
    while (true) {
        while (++i < last && !(*i < *(i-1))); // locate the first run
        if (!(i < last)) { // i has located the end of the last run
            if (m_first == first) return; // the range has only one run; sorting completed
            else { // the range has odd number of runs
                m_first = i = first; // start over
                continue;
            }
        }
        RandomIt m_middle(i); // the end of first run of merge; the begin of second run of merge
        while (++i < last && !(*i < *(i-1))); // locate the second run
        std::inplace_merge(m_first, m_middle, i); // merge
        if (i < last) m_first = i; // next
        else m_first = i = first; // start over
    }
}

• Best-case time complexity: \$O(n)\$ (which is better than typical merge sort)
• Average-case time complexity: \$O(n \log n)\$
• Worst-case time complexity: \$O(n \log n)\$
• Worst-case space complexity: \$O(n)\$
• Stability: true

This is slower than Timsort, right?

Answer 1

The algorithms in the standard library which care about order usually have an additional overload that takes a comparison function to replace operator<. It can be useful to compare instances of types that do not have an overloaded operator< or to compare things differently (for example, passing an instance of std::greater<> to std::sort will sort a collection in reverse order). Transforming your algorithm to take such a comparison function is more or less trivial:

template <class RandomIt, class Compare>
void RunAwareMergeSort(RandomIt first, RandomIt last, Compare compare) {
    RandomIt m_first(first); // the begin of first run of merge
    RandomIt i(first); // the locater
    while (true) {
        while (++i < last && !compare(*i, *(i-1))); // locate the first run
        if (!(i < last)) { // i has located the end of the last run
            if (m_first == first) return; // the range has only one run; sorting completed
            else { // the range has odd number of runs
                m_first = i = first; // start over
                continue;
            }
        }
        RandomIt m_middle(i); // the end of first run of merge; the begin of second run of merge
        while (++i < last && !compare(*i, *(i-1))); // locate the second run
        std::inplace_merge(m_first, m_middle, i, compare); // merge
        if (i < last) m_first = i; // next
        else m_first = i = first; // start over
    }
}

From a style point of view, your code could use more braces to avoid a potential Apple goto fail; bug and to let it breathe a bit more. Also, when you have to comment almost every line, it's almost always better to put the full explanation along the algorithm and not into it.

You also seemed to be concerned about the performance of your algorithm. I tested it with several patterns and compared it to several stable sorting algorithms that I had in a library. It always sorts an std::vector<int> with \$10^6\$ elements. Here are the results (Stable sort is std::stable_sort, yours is the natural mergesort, the other algorithms are not in the standard library):

As you can see, you algorithm is a bit better than Timsortfor its worst case (random data) and beats every other algorithm for the very specific "ascending sawtooth" pattern, which corresponds to a succession of ascending data (more or less log2(std::distance(first, last)) in our case). However, it slower than almost any other sorting algorithm whenever the data isn't mostly sorted in ascending order and it really doesn't like descending patterns.

Answer 2

You scan the natural runs, merge them pairwise. Then you do the second merge pass counting the (combined) runs once again, and so on. You could scan all the natural runs prior to merging them pairwise and store their respective lengths in a FIFO queue (call it \$Q\$). Now your algorithms would be conceptually something like

Q = scanRuns(array)
while Q.size() > 1
   left_length  = Q.dequeue()
   right_length = Q.dequeue()
   merge(..., left_length, right_length)
   Q.enqueue(left_length + right_length)

Also, since you use std::inplace_merge the space complexity of your algorithm is constant, yet that comes with a price: the worst case complexity (random data) of your implementation is actually \$\Theta(n \log n \log n)\$.

std::inplace_merge complexity (watch http://en.cppreference.com/w/cpp/algorithm/inplace_merge):

Exactly N-1 comparisons if enough additional memory is available, otherwise N·log(N) where N = std::distance(first, last).