Sort a Linked List Using Merge Sort in DSA C#

Mental Model

Break the list into smaller parts, sort each part, then join them back in order.

Analogy: Imagine sorting a messy deck of cards by splitting it into smaller piles, sorting each pile, then carefully merging the piles back into one sorted deck.

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

Dry Run Walkthrough

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

Goal: Sort the linked list so the nodes are in ascending order

Step 1: Split list into two halves

left: 4 -> 2 -> null
right: 1 -> 3 -> null

Why: We need smaller parts to sort easily

Step 2: Split left half again

left-left: 4 -> null
left-right: 2 -> null

Why: Keep splitting until parts have one node

Step 3: Merge left-left and left-right sorted lists

merged left: 2 -> 4 -> null

Why: Combine sorted parts into bigger sorted list

Step 4: Split right half again

right-left: 1 -> null
right-right: 3 -> null

Why: Split right half to single nodes

Step 5: Merge right-left and right-right sorted lists

merged right: 1 -> 3 -> null

Why: Combine sorted parts into bigger sorted list

Step 6: Merge merged left and merged right lists

final sorted: 1 -> 2 -> 3 -> 4 -> null

Why: Final merge gives fully sorted list

Result:

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

Annotated Code

DSA C#

using System;

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

public class Solution {
    // Merge two sorted lists into one sorted list
    private ListNode Merge(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        if (l1.val <= l2.val) {
            l1.next = Merge(l1.next, l2); // merge rest and link
            return l1;
        } else {
            l2.next = Merge(l1, l2.next); // merge rest and link
            return l2;
        }
    }

    // Find middle node to split list
    private ListNode GetMiddle(ListNode head) {
        if (head == null) return head;
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next; // move slow by 1
            fast = fast.next.next; // move fast by 2
        }
        return slow;
    }

    public ListNode SortList(ListNode head) {
        if (head == null || head.next == null) return head; // base case

        ListNode mid = GetMiddle(head); // find middle
        ListNode rightHead = mid.next;
        mid.next = null; // split list

        ListNode left = SortList(head); // sort left half
        ListNode right = SortList(rightHead); // sort right half

        return Merge(left, right); // merge sorted halves
    }

    public void PrintList(ListNode head) {
        ListNode curr = head;
        while (curr != null) {
            Console.Write(curr.val);
            if (curr.next != null) Console.Write(" -> ");
            curr = curr.next;
        }
        Console.WriteLine(" -> null");
    }

    public static void Main() {
        Solution sol = new Solution();
        ListNode head = new ListNode(4, new ListNode(2, new ListNode(1, new ListNode(3))));
        Console.WriteLine("Original list:");
        sol.PrintList(head);
        ListNode sorted = sol.SortList(head);
        Console.WriteLine("Sorted list:");
        sol.PrintList(sorted);
    }
}

if (head == null || head.next == null) return head; // base case

stop splitting when list has 0 or 1 node

ListNode mid = GetMiddle(head); // find middle

find middle node to split list into two halves

mid.next = null; // split list

break list into two separate lists

ListNode left = SortList(head); // sort left half

recursively sort left half

ListNode right = SortList(rightHead); // sort right half

recursively sort right half

return Merge(left, right); // merge sorted halves

combine two sorted lists into one sorted list

slow = slow.next; // move slow by 1

advance slow pointer to find middle

fast = fast.next.next; // move fast by 2

advance fast pointer twice as fast to find middle

l1.next = Merge(l1.next, l2); // merge rest and link

link smaller node and merge remaining nodes

l2.next = Merge(l1, l2.next); // merge rest and link

link smaller node and merge remaining nodes

Output

Original list:

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

Sorted list:

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

Complexity Analysis

Time: O(n log n) because the list is repeatedly split in half (log n splits) and merged (n work per merge)

Space: O(log n) due to recursion stack 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 C#

if (head == null || head.next == null) return head; // base case

single node list

returns the node as is, no sorting needed

DSA C#

if (head == null || head.next == null) return head; // base case

list with duplicate values

duplicates are kept and sorted correctly

DSA C#

if (l1.val <= l2.val) { ... } else { ... } in Merge function

When to Use This Pattern

When asked to sort a linked list efficiently, reach for merge sort because it sorts in O(n log n) time without extra array space.

Common Mistakes

Mistake: Not breaking the list into two halves properly causing infinite recursion
Fix: Set mid.next = null to split the list cleanly before recursive calls

Mistake: Merging lists incorrectly by not linking nodes properly
Fix: Use recursive merge that links smaller node and merges the rest

Summary

Sorts a linked list by splitting it into halves, sorting each half, and merging them.

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

The key insight is to split the list using slow/fast pointers and merge sorted halves recursively.

Practice

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

easy

A. It efficiently sorts the list in O(n log n) time without needing extra space for arrays.

B. It sorts the list in O(n^2) time but uses less memory.

C. It requires the list to be converted into an array first.

D. It only works for linked lists with integer values.

Solution

1. Step 1: Understand merge sort time complexity on linked lists

   Merge sort divides the list into halves recursively and merges them, achieving O(n log n) time.

2. Step 2: Compare space usage with other sorts

   Unlike quicksort or heapsort on arrays, merge sort on linked lists does not require extra array space, making it memory efficient.

3. Final Answer:

   It efficiently sorts the list in O(n log n) time without needing extra space for arrays. -> Option A

4. Quick Check:

   Merge sort = O(n log n) + memory efficient [OK]

Hint: Merge sort is best for linked lists due to O(n log n) and no extra arrays [OK]

Common Mistakes:

• Thinking merge sort uses extra array space for linked lists
• Confusing merge sort with bubble sort time complexity
• Assuming merge sort only works on arrays
• Believing merge sort requires integer-only lists

2. Which of the following is the correct way to split a linked list into two halves in C# for merge sort?

easy

A. Convert the list to an array and split the array.

B. Use a single pointer to count nodes and split at half index.

C. Use two pointers: slow moves 1 step, fast moves 2 steps; slow marks middle.

D. Split the list by removing the last node repeatedly.

Solution

1. Step 1: Identify the standard technique to find middle in linked list

   Using two pointers, slow and fast, where fast moves twice as fast, slow ends at middle.

2. Step 2: Explain why other options are incorrect

   Counting nodes requires extra traversal; converting to array is inefficient; removing last node is not splitting in half.

3. Final Answer:

   Use two pointers: slow moves 1 step, fast moves 2 steps; slow marks middle. -> Option C

4. Quick Check:

   Two-pointer technique = correct split [OK]

Hint: Use slow-fast pointers to find middle in one pass [OK]

Common Mistakes:

• Trying to split by counting nodes first
• Converting linked list to array unnecessarily
• Removing nodes instead of splitting
• Using only one pointer to find middle

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

medium

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

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

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

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

Solution

1. Step 1: Break down the list and sort halves recursively

   Split into (4 -> 2) and (1 -> 3). Sort each half: (2 -> 4) and (1 -> 3).

2. Step 2: Merge the two sorted halves

   Merge (2 -> 4) and (1 -> 3) to get (1 -> 2 -> 3 -> 4).

3. Final Answer:

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

4. Quick Check:

   Sorted ascending = 1,2,3,4 [OK]

Hint: Merge sorted halves step-by-step to get final sorted list [OK]

Common Mistakes:

• Not sorting halves before merging
• Merging without sorting causing wrong order
• Confusing node values during merge
• Forgetting to set last node's next to null

4. In the following C# merge sort code for linked list, what is the bug?

public ListNode MergeSort(ListNode head) {
  if (head == null || head.next == null) return head;
  ListNode mid = GetMiddle(head);
  ListNode left = MergeSort(head);
  ListNode right = MergeSort(mid);
  return Merge(left, right);
}

medium

A. The base case is incorrect; it should check for head.next.next.

B. The middle node is not disconnected from the left half, causing infinite recursion.

C. The Merge function is called before sorting the halves.

D. The GetMiddle function returns the last node instead of the middle.

Solution

1. Step 1: Identify the role of splitting the list

   After finding middle, the list must be split by setting middle's previous node next to null to separate halves.

2. Step 2: Explain the bug effect

   Without disconnecting, recursive calls keep processing the same list, causing infinite recursion or stack overflow.

3. Final Answer:

   The middle node is not disconnected from the left half, causing infinite recursion. -> Option B

4. Quick Check:

   Disconnect middle to avoid infinite recursion [OK]

Hint: Always break list into two by setting middle's previous next to null [OK]

Common Mistakes:

• Not disconnecting the list at middle
• Wrong base case conditions
• Calling merge before sorting halves
• Assuming GetMiddle returns last node

5. You have a linked list with nodes containing duplicate values: 3 -> 1 -> 2 -> 3 -> 2 -> null. After applying merge sort, what will be the correct sorted linked list?

hard

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

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

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

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

Solution

1. Step 1: Understand merge sort handles duplicates by sorting all nodes

   Merge sort compares node values and merges in ascending order, preserving duplicates in sorted order.

2. Step 2: Sort the list step-by-step

   Sorted order is 1, 2, 2, 3, 3, so the final list is 1 -> 2 -> 2 -> 3 -> 3 -> null.

3. Final Answer:

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

4. Quick Check:

   Duplicates sorted ascending = 1,2,2,3,3 [OK]

Hint: Merge sort keeps duplicates in sorted order naturally [OK]

Common Mistakes:

• Assuming duplicates get removed
• Mixing order of duplicate nodes
• Not sorting duplicates correctly
• Confusing stable sort with unstable sort