Merging lists

Two sorted linked lists can be merged into one sorted list without making a single new node. You only change next references. This is the main step of merge sort, and on a linked list it needs no extra arrays.

Merging two sorted lists

You met merging in SORT-2, on Python lists. The idea is the same: the smallest value left is at the front of one of the two lists, so compare the two fronts and take the smaller one.

On a linked list, “take” means “link it onto the end of the result”. Keep a name tail for the last node of the result, and start the result with a dummy node (lesson 2), so that the first node is not a special case:

def merge(a, b):
    dummy = tail = Node(None)
    while a is not None and b is not None:
        if a.value <= b.value:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a if a is not None else b
    return dummy.next

When one list runs out, the rest of the other list is already sorted and already linked. One assignment attaches all of it. Each pass of the loop does a fixed amount of work and moves one node, so merging lists of lengths n and m takes O(n + m) time and O(1) extra space.

Ties and stability

The merge takes from a when a.value <= b.value, using <= and not <. When two values are equal, the one from the first list goes first. So items with equal values keep their order. A sort that keeps equal items in their original order is called stable (SORT-7). With < the merge would still sort, but it would not be stable.

Merge sort on a linked list

Merge sort has three steps: split the list into two halves, sort each half, and merge them.

• Split: find the middle with slow and fast (lesson 5), then cut the list there by setting the middle node’s next to None. Use the version where slow stops on the first middle node, or a list of two nodes never splits.
• Sort each half: call merge sort on each one. A list of zero or one nodes is already sorted.
• Merge: the merge above.

The split is the step that is easy to get wrong:

slow, fast = head, head.next   # slow stops on the first middle node
while fast is not None and fast.next is not None:
    slow, fast = slow.next, fast.next.next
second = slow.next
slow.next = None               # cut the list in two

Now head and second are two lists of about half the length. Sort each one with a recursive call, and merge the two results. LINK-P6 asks you to put the whole sort together.

Each level of halving touches every node once, to split and to merge, and there are about log₂ n levels (the number of times you can halve n). So the time is O(n log n), the same as merge sort on an array.

The recursion is only about log₂ n calls deep: 17 for 100,000 nodes. That is well inside Python’s limit. And there is no extra array for the merge, which on a Python list needs O(n) extra space.

When to use a linked list

• Use one when you hold references to nodes and must insert or remove next to them in O(1): caches that move an item to the front (HASH-7), lists that are split and joined often, or the lists inside other structures, such as the buckets of a hash table (HASH-2).
• Do not use one when you read by position, or just add and remove at the ends. A Python list or a deque is faster and smaller.

Now try LINK-P6, Sort the train.