Stable merge sort for a singly linked chain in Java

Last updated: 1 Oct 20264 min read

tutorial

Linked merge sort repeatedly splits an acyclic chain and merges sorted halves, choosing the left node first when keys tie.

Split without indexed access

A slow cursor moves one link and a fast cursor moves two. Starting fast at head.next leaves the extra node on the left when the length is odd. Cut slow.next before recursing; without that cut, the left recursion still points into the right half and never reaches a smaller input.

Merge by relinking existing nodes. The comparison uses less than or equal so equal-priority records from the left half remain before equal-priority records from the right half. That is the stability contract; changing it to strict less than can reverse ties across halves.

Budget stack and ownership

This top-down version uses recursion depth O(log n) for splitting, unlike in-place group reversal. It does not allocate a second array or clone payload objects. Java's List.sort contract is a different API surface; this implementation exists for code that owns Node references.

Shared suffixes and cycles violate the independent-chain precondition. Detect shared tails or cycles before sorting untrusted node graphs.

Working program

public class SortDispatchChain {
    static final class Node {
        final String dispatchId;
        final int priority;
        Node next;
        Node(String dispatchId, int priority, Node next) {
            this.dispatchId = dispatchId; this.priority = priority; this.next = next;
        }
    }
    static Node sort(Node head) {
        if (head == null || head.next == null) return head;
        Node slow = head, fast = head.next;
        while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
        Node right = slow.next;
        slow.next = null;
        return merge(sort(head), sort(right));
    }
    static Node merge(Node left, Node right) {
        Node sentinel = new Node("sentinel", 0, null), tail = sentinel;
        while (left != null && right != null) {
            if (left.priority <= right.priority) { tail.next = left; left = left.next; }
            else { tail.next = right; right = right.next; }
            tail = tail.next;
        }
        tail.next = left != null ? left : right;
        return sentinel.next;
    }
    static String labels(Node head) {
        StringBuilder result = new StringBuilder();
        for (Node cursor = head; cursor != null; cursor = cursor.next) {
            if (result.length() > 0) result.append(",");
            result.append(cursor.dispatchId);
        }
        return result.toString();
    }
    public static void main(String[] args) {
        Node head = new Node("review-47", 47, new Node("ship-15", 15,
            new Node("hold-47", 47, new Node("pack-20", 20, null))));
        System.out.println(labels(sort(head)));
        System.out.println(sort(null) == null);
    }
}

Output

ship-15,pack-20,review-47,hold-47
true

Cost and ownership

Splitting and merging take O(n log n) time. Recursive call frames use O(log n) space; each merge allocates one short-lived sentinel, with O(n) such allocations over the full sort. Nodes and payloads are reused, so the returned root replaces the old one.

Common Mistakes

Do not leave the halves connected before recursion.
Do not choose the right node on equal keys if stable order matters.
Do not claim O(1) total auxiliary memory for this recursive implementation.