# Melsort — Sorting with encroaching lists

For the nth time already I come back with yet another alien sorting algorithm. Today I will present Melsort, implemented from the description I found in the paper Encroaching Lists as a Measure of Presortedness by Skiena.

### Melsort

Melsort is a two-step algorithm: first it constructs a set of encroaching lists, then it merges them all until there is only one sorted list left. The way it creates list is as follows: it takes the first element to sort and puts it in the first list, then for every other element it takes it, compares it to the head and the tail of the first list; if it is lesser than the head, it prepends it to the head of this list, and if it is greater than the tail, it appends it to the end of the list. If the element to sort is neither lesser than the head nor greater than the tail, it tries to perform the same checks and insertions with the second list, then the third, etc... If it can't fit any of the existing lists, it creates a new one and appends the element to it.

To make it clearer, imagine that we want to sort the following list: $\{1, 9, 2, 3, 4, 6, 7, 0, 5, 8\}$. The resulting lists $S_i$ will be $S_1 = \{0, 1, 9\}$, $S_2 = \{2, 3, 4, 6, 7, 8\}$ and $S_3 = \{5\}$. Then melsort will merge $S_3$ into $S_2$, then the resulting $S_2$ into $S_1$ and the resulting list will be sorted.

Note that for every resulting list, we have $head(S_n) \le head(S_{n+1})$ and $tail(S_n) \ge tail(S_{n+1})$. The authors decide to call the lists « encroaching » because of these specific patterns.

### Pseudocode

I wish I could copy and paste here the pseudo-code present in the paper, but I'm not sure about the legal ramifications... However, the paper describing neatsort also provides some pseucode for melsort, and I guess there isn't a problem with that one, so here we go:

Input: A list X of length n.
Output: the ordered version of the input list.
listCount := 1;
put X_1 in list_1;
for i := 2 to n do
for j := 1 to listCount do
if X_i < head(list_j) then
add X_i to the head of list_j;
break;
end
if X_i > tail(list_j) then
add X_i to the tail of list_j;
break;
end
end
if X_i couldn't be added to any list then
add 1 to listCount;
create list_listCount;
put X_i in the newly created list;
end
end
while listCount > 1
if odd(listCount) then
end
for i := 1 to listCount/2 do
end
listCount /:= 2;
end


You can look at the original neatsort paper if you want to have a prettier rendering of the pseudocode. In the version above, consider underscores to denote subscripts and thus indexing, not actual parts of the variable names.

### An implementation

Here is a C++14 implementation of the algorithm above, with the usual algorithm interface: it takes a pair of forward iterators and sorts the corresponding sequence with the given comparison function.

#include <algorithm>
#include <functional>
#include <iterator>
#include <list>
#include <utility>
#include <vector>

template<
typename ForwardIterator,
typename Compare = std::less<>
>
auto melsort(ForwardIterator first, ForwardIterator last, Compare compare={})
-> void
{
using value_type = typename std::iterator_traits<ForwardIterator>::value_type;
std::vector<std::list<value_type>> lists;

////////////////////////////////////////////////////////////
// Create encroaching lists

for (auto it = first ; it != last ; ++it)
{
bool found = false;
for (auto& list: lists)
{
if (not compare(list.front(), *it))
{
list.emplace_front(std::move(*it));
found = true;
break;
}
if (not compare(*it, list.back()))
{
list.emplace_back(std::move(*it));
found = true;
break;
}
}

{
lists.emplace_back();
lists.back().emplace_back(std::move(*it));
}
}

////////////////////////////////////////////////////////////
// Merge encroaching lists

while (lists.size() > 2)
{
if (lists.size() % 2 != 0)
{
auto last_it = std::prev(std::end(lists));
auto last_1_it = std::prev(last_it);
last_1_it->merge(*last_it, compare);
lists.pop_back();
}

auto first_it = std::begin(lists);
auto half_it = first_it + lists.size() / 2;
while (half_it != std::end(lists))
{
first_it->merge(*half_it, compare);
++first_it;
++half_it;
}

lists.erase(std::begin(lists) + lists.size() / 2, std::end(lists));
}

// Merge lists back into the original collection

if (lists.size() == 2)
{
merge_move(
std::begin(lists.front()), std::end(lists.front()),
std::begin(lists.back()), std::end(lists.back()),
first, compare
);
}
else if (lists.size() == 1)
{
std::move(std::begin(lists.front()), std::end(lists.front()), first);
}
}


The overall merging strategy is the one described on the pseudo-code in the paper: we could merge the last two lists until there is only one left, but for some reason the original paper merges both halves of the set of lists at each pass. I tried both merging strategies, and this one looked faster in my benchmarks.

The merge_move function is simply an equivalent of std::merge that moves the elements to merge instead of copying them. It was introduced by Eric Niebler and proposed for standardization in the Ranges TS:

template<
typename InputIterator1,
typename InputIterator2,
typename OutputIterator,
typename Compare = std::less<>
>
auto merge_move(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare compare={})
-> OutputIterator
{
for (; first1 != last1; ++result)
{
if (first2 == last2)
{
return std::move(first1, last1, result);
}

if (compare(*first2, *first1))
{
*result = std::move(*first2);
++first2;
}
else
{
*result = std::move(*first1);
++first1;
}
}
return std::move(first2, last2, result);
}


I decided to use it when there are only two lists left to combine the final merge and move to the original collection when possible.

### To go further

If you read the original paper, you can notice some differences: for example, it uses a binary search to find in which list to insert the next element (which reduces the complexity to $O(n \log{n})$), but I never managed to improve the performance with such a binary search. The original paper also has a discussion about reducing the space used to $O(\sqrt{n})$, but to be honest I couldn't understand what was described, and that space optimization wasn't in the pseudocode.

Note that the algorithm as implemented is extremely slow. The original paper claims that it can be as fast if not faster than mergesort, but papers citing melsort tend to consider that it is really slow despite its excellent time complexity, so...

Is there anything I can change to improve the algorithm, without actually turning it into a different sorting algorithm?

Note: as an interesting note, melsort seems to be close to patience sort. It almost corresponds to the Patience+ sort as described by Chandramouli and Goldstein in Patience is a Virtue: Revisiting Merge and Sort on Modern Processors.

• I don't sepose the paper has a URL link we could add to the question. – Martin York Apr 6 '16 at 19:38
• @LokiAstari Unfortunately, I don't think so. I wish all these papers were available for free. – Morwenn Apr 6 '16 at 19:40
• Given that you only ever add items to the beginning or end of a list (never the middle), one obvious possibility would be to use std::deques instead of std::lists. Would/will require quite bit of rewriting (since you'd have to use std::merge instead of list.merge) but unless you're sorting quite large objects, likely to improve speed. – Jerry Coffin Apr 6 '16 at 23:10
• @JerryCoffin That's what I did at first, but... the merge step screams for a list instead :p – Morwenn Apr 6 '16 at 23:11

I have not benchmarked this, so take this with a grain of salt.

In the merge step you are iterating over the lists repeatedly. If you consider a pathological case that results in $\frac{n}{2}$ lists of $2$ elements each. Then on the first step you reduce to $\frac{n}{4}$ lists of $4$ elements each if I read your code correctly, then $\frac{n}{8}$ lists and so forth.

This means you will do $\log_2\left(n\right)$ passes and in each pass you will iterate once over all $n$ elements. Giving you $\mathcal{O}\left(n\cdot\log_2\left(n\right)\right)$ steps through the linked list.

Iterating through all elements in a linked list is $\mathcal{O}\left(n\right)$ just as it is for a vector. But in my experience the constant factor for iterating through a list is is a lot larger than for a vector, I'm not talking about 10-20% but more like 300-2000% larger.

This is due to the difference in locality of reference, for a vector it is contiguous memory accesses and the CPU's prefetcher is going to ❤❤❤ you for it. However for a list you have to chase the pointers and worst case is you get a cache miss on every pointer (can happen if your list size exceeds the CPU cache size) in the list resulting in a $\approx200$ cycle delay on each node. A custom allocation strategy for list nodes can mitigate this to some degree but it is like putting a band-aid on a stab wound, you need stitches.

My gut feeling is that the $\mathcal{O}\left(n\right)$ insertion time at the head of a vector in the encroaching phase is going to be recovered and then some in the merge phase due to higher locality of reference. But as always you should benchmark to find out.

In fact I think you might be able to use std::deque that has $\mathcal{O}\left(1\right)$ insertion at the front and random access. However I believe that std::deque is implemented as a list of vectors, in which case the size of the vectors is important, this is one of these cases where a custom data structure might benefit you.

The worst case for this algorithm is a list made of two interleaved lists: one increasing from the bottom, the other one decreasing from top, like this:

0, 9, 1, 8, 2, 7, 3, 6, 4, 5


Such data would cause the routine to build $N/2$ lists, two items each. The straightforward implementation would then require $O(N)$ failed searches to make a new list every second input item.

One might create for example additional array of references to those lists and keep it sorted by the head's value of each list – that would allow fast (binary) search for a list to add the new item. However, that would also require extending the array with every new list added, possibly with data relocation if a new list falls between those created before. The overhead would probably eat the gain. And another array would be needed for searching a list to append the item at the list's end.

Another approach: a self-organizing tree, say AVL, splay or B-tree instead of an array, might give comparable gain on search at a much smaller housekeeping cost.

• The ironic part of that worst case is that you can perform a single merge between the heads and the tails to sort it in one operation .______. – Morwenn Apr 6 '16 at 21:22
• The good thing is that the heads are already sorted and the tails are already reverse sorted, so a single binary search checking if Xi < head_j || Xi > tail_j is enough, but it proved to be slower than the linear search from older to newer list in practice. – Morwenn Apr 6 '16 at 21:25
• No naked loops

As usual, I recommend factoring out build and merge phases into functions of their own.

• Correct me if I am wrong, the code prepends the item to the list if it compares equal to the head. It is not what the pseudocode describes. In any case, is there a benefit of not compare(list.front(), *it) vs compare(*it, list.front())? Stability is lost either way (not that the original algorithm is stable - but that may possibly be fixed).

• Merging strategy

It looks like an opportunistic optimization. They try to keep lists more or less balanced. If two last lists are always merged, the last list grows too large, and overall merge performance degrades towards quadratic.

Always merging two shortest lists should give better performance guarantees (however actual performance may suffer).

• The not thingy probably comes from when I tried the other merging strategy (always merge the two last lists), in which case the not ensured that the first lists were more likely to be bigger than the last ones. – Morwenn Apr 6 '16 at 21:32
• Also, I understand you recommend no having naked loops, but I really don't like reserving names and making "artificial" functions that are actually so specific that you know that you can't reuse them anywhere. Here, the lists object is clearly "global" to the function, and I hardly see why I would create functions taking or returning an std::vector<std::list>> outside of this algorithm. It may even be the first time I need such a thing :/ – Morwenn Apr 6 '16 at 21:54