Sort a Linked List Using Merge Sort in DSA Java

Mental Model

Split the list into halves, sort each half, then merge them back in order. Repeat until the whole list is sorted.

Analogy: Imagine sorting a deck of cards by splitting it into smaller piles, sorting each pile, then carefully merging the piles back together in order.

head -> 4 -> 2 -> 1 -> 3 -> null

Dry Run Walkthrough

Input: list: 4 -> 2 -> 1 -> 3 -> null

Goal: Sort the linked list in ascending order using merge sort

Step 1: Find middle to split list into two halves

First half: 4 -> 2 -> null
Second half: 1 -> 3 -> null

Why: Splitting helps break down the problem into smaller parts

Step 2: Recursively sort first half (4 -> 2)

Split into 4 -> null and 2 -> null
Sort each: 4 -> null and 2 -> null

Why: Base case reached when list has one element

Step 3: Merge sorted halves 4 -> null and 2 -> null

2 -> 4 -> null

Why: Merge two sorted lists into one sorted list

Step 4: Recursively sort second half (1 -> 3)

Split into 1 -> null and 3 -> null
Sort each: 1 -> null and 3 -> null

Why: Base case reached when list has one element

Step 5: Merge sorted halves 1 -> null and 3 -> null

1 -> 3 -> null

Why: Merge two sorted lists into one sorted list

Step 6: Merge two sorted halves 2 -> 4 -> null and 1 -> 3 -> null

1 -> 2 -> 3 -> 4 -> null

Why: Final merge produces fully sorted list

Result:

1 -> 2 -> 3 -> 4 -> null

Annotated Code

DSA Java

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; this.next = null; }
}

public class MergeSortLinkedList {

    public static ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head; // base case: 0 or 1 node

        // find middle using slow and fast pointers
        ListNode slow = head, fast = head, prev = null;
        while (fast != null && fast.next != null) {
            prev = slow; // keep track of node before slow
            slow = slow.next; // move slow by 1
            fast = fast.next.next; // move fast by 2
        }
        prev.next = null; // split list into two halves

        ListNode l1 = sortList(head); // sort first half
        ListNode l2 = sortList(slow); // sort second half

        return merge(l1, l2); // merge sorted halves
    }

    private static ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                tail.next = l1; // attach smaller or equal node
                l1 = l1.next; // advance l1
            } else {
                tail.next = l2; // attach smaller node
                l2 = l2.next; // advance l2
            }
            tail = tail.next; // advance tail
        }

        tail.next = (l1 != null) ? l1 : l2; // attach remaining nodes
        return dummy.next;
    }

    public static void printList(ListNode head) {
        ListNode curr = head;
        while (curr != null) {
            System.out.print(curr.val);
            if (curr.next != null) System.out.print(" -> ");
            curr = curr.next;
        }
        System.out.print(" -> null\n");
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(4);
        head.next = new ListNode(2);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(3);

        ListNode sorted = sortList(head);
        printList(sorted);
    }
}

if (head == null || head.next == null) return head;

base case: list with 0 or 1 node is already sorted

while (fast != null && fast.next != null) { prev = slow; slow = slow.next; fast = fast.next.next; }

find middle node to split list into two halves

prev.next = null;

split list into two separate lists

ListNode l1 = sortList(head); ListNode l2 = sortList(slow);

recursively sort each half

return merge(l1, l2);

merge two sorted halves into one sorted list

while (l1 != null && l2 != null) { if (l1.val <= l2.val) { tail.next = l1; l1 = l1.next; } else { tail.next = l2; l2 = l2.next; } tail = tail.next; }

merge nodes by choosing smaller or equal value each step

tail.next = (l1 != null) ? l1 : l2;

attach remaining nodes after one list is exhausted

Output

1 -> 2 -> 3 -> 4 -> null

Complexity Analysis

Time: O(n log n) because the list is split in half log n times and merging takes O(n) each time

Space: O(log n) due to recursion stack depth from splitting the list

vs Alternative: Compared to bubble or insertion sort on linked list which is O(n^2), merge sort is much faster for large lists

Edge Cases

empty list

returns null immediately without error

DSA Java

if (head == null || head.next == null) return head;

single element list

returns the single node as sorted list

DSA Java

if (head == null || head.next == null) return head;

list with duplicate values

duplicates are kept and sorted correctly

DSA Java

while (l1 != null && l2 != null) { if (l1.val <= l2.val) ... }

When to Use This Pattern

When you need to sort a linked list efficiently, especially with no random access, reach for merge sort because it splits and merges lists using pointers without extra array space.

Common Mistakes

Mistake: Not splitting the list correctly by forgetting to disconnect the first half from the second
Fix: Set prev.next = null to break the list into two halves

Mistake: Merging lists incorrectly by not advancing pointers properly
Fix: Advance the pointer (l1 or l2) after attaching its node to the merged list

Summary

Sorts a linked list in ascending order using merge sort by splitting, sorting, and merging.

Use when you want an efficient O(n log n) sort for linked lists without extra array space.

The key insight is to split the list into halves recursively and merge sorted halves back together.

Practice

1. What is the main advantage of using merge sort to sort a linked list compared to quicksort?

easy

A. Merge sort is easier to implement with arrays than linked lists.

B. Quicksort is faster on linked lists because it uses less memory.

C. Merge sort does not require random access and works well with linked lists.

D. Quicksort always sorts linked lists in O(n) time.

Solution

1. Step 1: Understand linked list access

   Linked lists do not support fast random access, so algorithms needing it perform poorly.

2. Step 2: Compare merge sort and quicksort

   Merge sort splits and merges lists using pointers, avoiding random access, making it efficient for linked lists.

3. Final Answer:

   Merge sort does not require random access and works well with linked lists. -> Option C

4. Quick Check:

   Merge sort suits linked lists better than quicksort [OK]

Hint: Merge sort fits linked lists due to pointer-based splitting [OK]

Common Mistakes:

• Thinking quicksort is always faster on linked lists
• Assuming arrays and linked lists behave the same
• Ignoring random access needs

2. Which of the following is the correct base case condition in the merge sort function for a linked list?

easy

A. if (head == null) return head.next;

B. if (head == null || head.next == null) return head;

C. if (head.next == null) return null;

D. if (head == null && head.next == null) return null;

Solution

1. Step 1: Identify base case for recursion

   When the list is empty or has one node, it is already sorted.

2. Step 2: Check condition correctness

   Condition 'head == null || head.next == null' correctly checks for empty or single-node list.

3. Final Answer:

   if (head == null || head.next == null) return head; -> Option B

4. Quick Check:

   Base case returns head if list size ≤ 1 [OK]

Hint: Base case: empty or single node list returns itself [OK]

Common Mistakes:

• Using && instead of || in base case
• Returning null incorrectly for single node
• Not handling empty list properly

3. Given the linked list: 4 -> 2 -> 1 -> 3 -> null, what is the sorted linked list after applying merge sort?

medium

A. 1 -> 2 -> 3 -> 4 -> null

B. 4 -> 3 -> 2 -> 1 -> null

C. 1 -> 3 -> 2 -> 4 -> null

D. 2 -> 1 -> 3 -> 4 -> null

Solution

1. Step 1: Split the list into halves

   Split into (4 -> 2) and (1 -> 3).

2. Step 2: Recursively sort halves and merge

   Sort (4 -> 2) to (2 -> 4), sort (1 -> 3) to (1 -> 3), then merge to (1 -> 2 -> 3 -> 4).

3. Final Answer:

   1 -> 2 -> 3 -> 4 -> null -> Option A

4. Quick Check:

   Sorted list ascending order [OK]

Hint: Merge sorted halves to get fully sorted list [OK]

Common Mistakes:

• Not splitting list correctly
• Merging without sorting halves
• Mixing node order during merge

4. Identify the error in this merge function snippet for linked lists:

Node merge(Node a, Node b) {
  if (a == null) return b;
  if (b == null) return a;
  if (a.data < b.data) {
    a.next = merge(a.next, b);
    return b;
  } else {
    b.next = merge(a, b.next);
    return a;
  }
}

medium

A. The function does not merge nodes recursively.

B. The base cases do not handle null nodes.

C. The comparison operator should be <= instead of <.

D. The function returns the wrong node after recursion.

Solution

1. Step 1: Analyze return statements

   When a.data < b.data, function should return 'a' but returns 'b' incorrectly.

2. Step 2: Correct return node after recursion

   Return the node chosen as smaller to maintain sorted order; here it should be 'a' or 'b' accordingly.

3. Final Answer:

   The function returns the wrong node after recursion. -> Option D

4. Quick Check:

   Return chosen smaller node to merge correctly [OK]

Hint: Return the smaller node after recursive merge [OK]

Common Mistakes:

• Returning wrong node after recursive call
• Ignoring base cases
• Incorrect comparison operator

5. You have a linked list with nodes: 5 -> 3 -> 8 -> 2 -> 7 -> null. After applying merge sort, what is the correct sorted linked list? Also, explain why merge sort is preferred over bubble sort for this linked list.

hard

A. 2 -> 3 -> 5 -> 7 -> 8 -> null; Merge sort is faster and uses less memory on linked lists.

B. 8 -> 7 -> 5 -> 3 -> 2 -> null; Bubble sort is faster for small lists.

C. 2 -> 3 -> 5 -> 7 -> 8 -> null; Bubble sort is preferred because it is simpler.

D. 5 -> 3 -> 8 -> 2 -> 7 -> null; Merge sort does not work on linked lists.

Solution

1. Step 1: Sort the list using merge sort

   Sorted order is 2 -> 3 -> 5 -> 7 -> 8 -> null after splitting and merging.

2. Step 2: Explain merge sort advantage

   Merge sort is O(n log n) and uses pointers efficiently; bubble sort is O(n²) and inefficient for linked lists.

3. Final Answer:

   2 -> 3 -> 5 -> 7 -> 8 -> null; Merge sort is faster and uses less memory on linked lists. -> Option A

4. Quick Check:

   Sorted list + merge sort efficiency [OK]

Hint: Merge sort is efficient and stable for linked lists [OK]

Common Mistakes:

• Confusing bubble sort as faster
• Incorrect sorted order
• Thinking merge sort can't handle linked lists