I understand.

My point was that for some datasets, known to have long already sorted sequences, it just is worth it, compared to plain top-down or bottom-up, or the code complexity of detecting sorted sequences efficiently in a bottom-up merge sort.

Consider a list that is basically a concatenation of three sorted lists. Let's also assume that the second list is at least as long as the third list, for simplicity.

The first list is detected as sorted in the first pass. The first recursive call detects the rest of the second list, and recurses into the third list. The second recursive calls (two calls at the same depth) detect the entire list as sorted. After the merges, all the data is sorted.

This approach works extremely well when the input is mostly sorted. When the input has random sequences, the performance "degrades" gracefully to the top-down merge-sort level, while the code itself is very simple.

Overall, given a mix of almost-sorted data, with a few random sequences (and rarely a purely random list), I just believe this approach is valid. Sure, there are known faster methods, but the simplicity of the code makes this very attractive.

Remember: complex code can have complex bugs, too. In many real world cases, maintainability is more important than a few percent of run time difference.

Simply put, I am not convinced yet that there are good bottom-up variants for almost-sorted data.

In particular, consider datasets that are (for whatever reason) usually a few sorted lists concatenated, maybe with a few random nodes sprinkled in, and very rarely completely random lists. (So, no hard limits, just usually almost sorted, very rarely random.)

One approach is a mix, using an initial exploratory pass of the data to see if and where the input contains continuous sorted runs. If there are too many of them (as one can consider a single node as a continuous run of length 1), you fall back to a bottom-up merge sort. (Is there an efficient method to detect unsorted runs? So one could use bottom-up merge sort for unsorted runs, and merge them with sorted runs? Linked list traverses are expensive, so I don't think so.)

What I'd like to see best, is a theoretically sound method of merging a continuous run of sorted nodes (encountered during the bottom-up scan) into the bottom-up doubling-length list array.

(I'm pretty sure there is one. You always know the length of the continuous run; perhaps splitting it into power of two lengths? Or even detecting continuous sorted nodes of power-of-two lengths, and merging them directly to the corresponding arrays? What about order stability?)

Please do note that I'mnotclaiming you are incorrect; I am just saying I am not convinced yet -- and I suspect that some other members reading this thread share my sentiment. You may very well be right, but I just need to see proof -- for me that means an example.

I must also say that I much prefer seeing the salient code point inline in this post; downloading, extracting, and opening a ZIP file from who knows where (okay, your personal site ) is quite tedious, considering that we're just discussing interesting stuff, not doing in-depth research or actual work. At least I'm here for fun..

Having a full ZIP file test case would be very nice as an addition, if the salient part, the important function, was inline in the message here. Just my opinion, though.