Sort List

def sortList(next, values):
    # Collect the values of the nodes on the list, then sort them.
    on_list = []
    node = 0
    while node != -1:
        on_list.append(values[node])
        node = next[node]
    on_list.sort()
    return on_list

def sortList(next, values):
    def merge(a, b):
        # Splice two sorted lists into one; on a tie the node from a goes first.
        head = tail = -1
        while a != -1 and b != -1:
            if values[b] < values[a]:
                node, b = b, next[b]
            else:
                node, a = a, next[a]
            if tail == -1:
                head = node
            else:
                next[tail] = node
            tail = node
        next[tail] = a if a != -1 else b  # attach whatever is left
        return head

    def sort(head):
        if next[head] == -1:  # one node is already sorted
            return head
        # slow stops on the last node of the first half
        slow, fast = head, next[head]
        while fast != -1 and next[fast] != -1:
            slow = next[slow]
            fast = next[next[fast]]
        second = next[slow]
        next[slow] = -1  # cut the list in two
        return merge(sort(head), sort(second))

    result = []
    node = sort(0)
    while node != -1:
        result.append(values[node])
        node = next[node]
    return result