# Run-aware merge sort

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?

• For the sake of terminology: the algorithm is called natural merge sort. – coderodde Nov 14 '15 at 14:24
• I downvoted because I find the question unclear. Are you really asking "is this algorithm slower than some other algorithm measured in some specific way", or are you asking for improvements on the code? – Juho Nov 15 '15 at 10:26

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.

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).

• std::inplace_merge tries to get temporary buffer. If it is succesful, my implementation's worst time complexity will be O(n log n) as usual. If it fails, you will be right, it will be O(n log²n). – Dannyu NDos Nov 22 '15 at 0:51
• @DannyuNDos: In-place, does require just O(1) temporary storage on the stack. – DrProgrammer Nov 22 '15 at 17:05
• libc++ implementation of std::inplace_merge may allocate up to n/2 additional memory and the one in libstdc++ may allocate up to n additional memory. This hardly falls into the O(1) space complexity category. – Morwenn Dec 14 '15 at 18:58