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.MelsortMelsort 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.PseudocodeI 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;    endendwhile listCount > 1    if odd(listCount) then        head(listCount - 1) := merge(head(listCount - 1), head(listCount));    end    for i := 1 to listCount/2 do        head(i) := merge(head(i), head(listCount/2 + i));    end    listCount /:= 2;endYou 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 implementationHere 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;            }        }        if (not found)        {            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 furtherIf 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.
Melsort  Sorting with encroaching lists
c++;algorithm;sorting;c++14