Sort a Linked List Using Merge Sort in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Merge Sort on a Linked List

What is the printed state of the linked list after applying merge sort on this list?

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

DSA C#

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

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

Node GetMiddle(Node head) {
    Node slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

Node Merge(Node l1, Node l2) {
    Node dummy = new Node(0);
    Node current = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }
    current.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

// After calling MergeSort on the initial list, print the list nodes in order.

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

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

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

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

💡 Hint

Think about how merge sort divides and merges the list in sorted order.

Merge sort splits the list into halves recursively and merges them back in sorted order. The final sorted list is 1 -> 2 -> 3 -> 4 -> null.

🧠 Conceptual

intermediate

Why Use Merge Sort for Linked Lists?

Why is merge sort preferred over quicksort for sorting linked lists?

A Because merge sort uses less memory than quicksort on arrays.

B Because quicksort is faster but uses more memory for linked lists.

C Because merge sort does not require random access and works efficiently with linked lists.

D Because quicksort cannot be implemented on linked lists.

💡 Hint

Think about how linked lists store elements and how merge sort accesses them.

Merge sort works well with linked lists because it only needs sequential access and can split and merge lists efficiently without random access. Quicksort requires random access which linked lists do not support efficiently.

🔧 Debug

advanced

Identify the Bug in Merge Function

What error will occur when running this merge function on two sorted linked lists?

DSA C#

Node Merge(Node l1, Node l2) {
    Node dummy = new Node(0);
    Node current = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }
    current.next = l1;
    current.next = l2;
    return dummy.next;
}

A Syntax error due to missing semicolon.

B The last assignment overwrites current.next causing loss of remaining nodes from l1 or l2.

C Infinite loop because current is never updated.

D NullReferenceException because current is null inside the loop.

💡 Hint

Look carefully at how current.next is assigned after the loop.

The code assigns current.next twice after the loop, so the first assignment is overwritten. This causes the remaining nodes from either l1 or l2 to be lost, resulting in an incomplete merged list.

📝 Syntax

advanced

Correct Syntax for Recursive Merge Sort Call

Which option correctly calls merge sort recursively on the two halves of a linked list?

DSA C#

Node MergeSort(Node head) {
    if (head == null || head.next == null) return head;
    Node mid = GetMiddle(head);
    Node rightHead = mid.next;
    mid.next = null;
    // Recursive calls here
    ???
}

A

Node left = MergeSort(head);
Node right = MergeSort(rightHead);

B

Node left = MergeSort(head.next);
Node right = MergeSort(mid);

C

Node left = MergeSort(mid);
Node right = MergeSort(rightHead.next);

D

Node left = MergeSort(rightHead);
Node right = MergeSort(head);

💡 Hint

Remember to split the list at mid and call merge sort on each half starting at head and rightHead.

After splitting the list at mid, the left half starts at head and the right half starts at rightHead. Recursive calls must be made on these two heads.

🚀 Application

expert

Number of Recursive Calls in Merge Sort

Given a linked list of 8 nodes, how many total calls to MergeSort will be made during the full sort?

A 15

B 7

C 8

D 16

💡 Hint

Think about how merge sort splits the list and how many nodes are processed at each level.

Merge sort splits the list into halves recursively until single nodes remain. For 8 nodes, the total calls equal 2*n - 1 = 15.

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