Return to Question

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.

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 := n 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
        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;
end

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
        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;
end

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, 8\}\$. Then melsort will merge \$S_3\$ into \$S_2\$, then the resulting \$S_2\$ into \$S_1\$ and the resulting list will be sorted.

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.