Merge Sort for Linked List (Optimized Iterative Approach) – java

After solving merge sort on a linked list using recursion, I started thinking about optimization. The recursive approach works well, but it uses extra space due to the recursion stack.

So I explored how to make it more efficient in terms of space.

What I Already Knew

• Merge sort is the best choice for linked lists
• Time complexity is already optimal: O(n log n)
• Recursive approach uses extra stack space: O(log n)

So the goal was not to improve time, but to reduce space usage.

Key Idea

Instead of using recursion, I thought:

What if I simulate merge sort iteratively?

This leads to a bottom-up merge sort approach.

How I Thought About It

In recursive merge sort:

• We divide the list until single nodes
• Then merge them back

In iterative merge sort:

• Start with sublists of size 1
• Merge pairs to make size 2
• Then merge size 2 lists to make size 4
• Continue doubling until the whole list is sorted

Step-by-Step Approach

1. Find the length of the linked list
2. Start with sublist size = 1
3. Split the list into parts of size size
4. Merge adjacent parts
5. Double the size each iteration

Code

class Solution {
    public Node mergeSort(Node head) {
        if (head == null || head.next == null) return head;

        int length = getLength(head);
        Node dummy = new Node(0);
        dummy.next = head;

        for (int size = 1; size < length; size *= 2) {
            Node curr = dummy.next;
            Node tail = dummy;

            while (curr != null) {
                Node left = curr;
                Node right = split(left, size);
                curr = split(right, size);

                tail.next = merge(left, right);

                while (tail.next != null) {
                    tail = tail.next;
                }
            }
        }
        return dummy.next;
    }

    private int getLength(Node head) {
        int len = 0;
        while (head != null) {
            len++;
            head = head.next;
        }
        return len;
    }

    private Node split(Node head, int size) {
        for (int i = 1; head != null && i < size; i++) {
            head = head.next;
        }

        if (head == null) return null;

        Node second = head.next;
        head.next = null;
        return second;
    }

    private Node merge(Node a, Node b) {
        Node dummy = new Node(0);
        Node curr = dummy;

        while (a != null && b != null) {
            if (a.data <= b.data) {
                curr.next = a;
                a = a.next;
            } else {
                curr.next = b;
                b = b.next;
            }
            curr = curr.next;
        }

        if (a != null) curr.next = a;
        if (b != null) curr.next = b;

        return dummy.next;
    }
}

Why This Works

Instead of breaking the list recursively, I am:

• Iteratively grouping nodes
• Merging them in increasing sizes

At each stage:

• Smaller sorted lists are merged into larger sorted lists

This continues until the entire list becomes sorted.

Example Walkthrough

Input:

40 -> 20 -> 60 -> 10

Step 1 (size = 1):

(40)(20)(60)(10)

Step 2 (size = 2):

(20 -> 40)(10 -> 60)

Step 3 (size = 4):

(10 -> 20 -> 40 -> 60)

Final result is sorted.

Complexity

Time Complexity: O(n log n)
Space Complexity: O(1)

There is no recursion, so no extra stack space is used.

Important Observations

• This approach avoids recursion completely
• It is more efficient for very large inputs
• Slightly harder to implement compared to recursive version
• Uses pointer manipulation carefully

Conclusion

The recursive solution is easier to understand, but the iterative approach is more space-efficient.

The key shift in thinking was:

• Moving from "divide recursively" to "merge iteratively in levels"

This helped me understand how merge sort can be adapted even further depending on constraints.

If you are preparing for interviews, knowing both approaches gives you an advantage.