I am trying to implement in C# the pseudocode from Wikipedia for "BottomUp implementation using lists".

Here is the pseudocode - and it is not what one would expect - for example, the length of the sublists doesn't grow twice, but is just incremented... :

function merge_sort(node head) is
    // return if empty list
    if head = nil then
        return nil
    var node array[32]; initially all nil
    var node result
    var node next
    var int  i
    result := head
    // merge nodes into array
    while result ≠ nil do
        next := result.next;
        result.next := nil
        for (i = 0; (i < 32) && (array[i] ≠ nil); i += 1) do
            result := merge(array[i], result)
            array[i] := nil
        // do not go past end of array
        if i = 32 then
            i -= 1
        array[i] := result
        result := next
    // merge array into single list
    result := nil
    for (i = 0; i < 32; i += 1) do
        result := merge(array[i], result)
    return result

They don't provide the merge() function as it is similar to those in other implementations.

My full C# code is below.

Could someone help with code, preferably C#, that really implements merge-sort on lists?

My translation of the pseudocode above:

public static LinkedList? MSortList(LinkedListNode input)  // MergeSortExternal
{
    if (input == null) return null;

    var result = input;
    LinkedListNode? next = null;
    var workArea = new LinkedListNode?[32];

    while(result != null)
    {
        var i = 0;
        do
        {
            next = result.Next;
            result = new LinkedListNode(result.Value);
            result = Merge(workArea[i], result);
            workArea[i] = null;
            if (i == 31) i--;
            i++;
            workArea[i] = result;
            result = next;
        } while (result != null && i < 32 && workArea[i] != null);
    }

    result = null;
    for(var i = 0; i < 32; i++)
    {
        result = Merge(workArea[i], result);
    }
    return result.List;
}

private static LinkedListNode Merge(LinkedListNode node1, LinkedListNode node2)
{
    var resultList = new LinkedList();
    while(node1 != null && node2 != null)
    {
        if(node1.Value <= node2.Value)
        {
            resultList.AddLast(node1.Value);
            node1 = node1.Next;
        }
        else
        {
            resultList.AddLast(node2.Value);
            node2 = node2.Next;

        }
    }

    var remaining = (node1 != null) ? node1 : node2;
    while(remaining != null)
    {
        resultList.AddLast(remaining.Value);
        remaining = remaining.Next;
    }

    return resultList.First;
}

Could someone help with code, preferably C#, that really implements merge-sort on lists?