import random

class LL(object):
    __slots__ = "value", "next"
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

def mklist(initializer):
    it = reversed(initializer)
    try:
        x = next(it)
    except StopIteration:
        return None # empty list is None
    else:
        head = LL(x)
        for value in it:
            head = LL(value, head)
        return head

def walk(head):
    while head is not None:
        yield head.value
        head = head.next

def tolist(head):
    return list(walk(head))

def listsort(head):
    """Translation from C to Python of listsort() [1].

    [1]: http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.c
    """
    if head is None: # empty list is already sorted
        return head

    insize = 1
    while True:
        p = head
        head, tail = None, None
        nmerges = 0 # count number of merges we do in this pass
        while p:
            nmerges += 1 # there exists a merge to be done
            q = p # step `insize' places along from p
            psize = 0
            for _ in range(insize):
                psize += 1
                q = q.next
                if q is None:
                    break
            # if q hasn't fallen off end, we have two lists to merge
            qsize = insize
            # now we have two lists; merge them
            while psize > 0 or (qsize > 0  and q is not None):
                # decide whether next element of merge comes from p or q
                if psize == 0:
                    # p is empty; e must come from q
                    e, q = q, q.next
                    qsize -= 1
                elif qsize == 0 or q is None:
                    # q is empty; e must come from p
                    e, p = p, p.next
                    psize -= 1
                elif p.value <= q.value:
                    # first element of p is lower (or same); e must come from p
                    e, p = p, p.next
                    psize -= 1
                else:
                    # first element of q is lower; e must come from q
                    e, q = q, q.next
                    qsize -= 1

                # add the next element to the merged list
                if tail is not None:
                    tail.next = e
                else:
                    head = e

                tail = e
            # now p has stepped `insize' places along, and q has too
            p = q

        tail.next = None
        # if we have done only one merge, we're finished
        if nmerges <= 1: # allow for nmerges==0, the empty list case
            return head
        # otherwise repeat, merging lists twice the size
        insize *= 2

def test():
    for n, r, k in product(range(14), repeat=3):
        L = list(range(n)) + [n//2]*r + [n-1]*k
        random.shuffle(L)
        head = mklist(L)
        head = listsort(head)
        result = tolist(head)
        assert result == sorted(L)

test()