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 the following list?

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

DSA C

struct Node {
    int data;
    struct Node* next;
};

// Assume mergeSort and helper functions are correctly implemented
// After mergeSort is called on the head of the list
// The list is printed using printList function

// Initial list: 4 -> 2 -> 1 -> 3 -> null
// After mergeSort, what is the output?

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

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

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

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

💡 Hint

Merge sort splits the list and merges sorted halves.

Merge sort on linked list sorts nodes in ascending order by splitting and merging sorted halves.

🧠 Conceptual

intermediate

Why Use Merge Sort for Linked Lists?

Why is merge sort preferred over quicksort for sorting a linked list?

A Because merge sort uses less memory than quicksort on arrays

B Because merge sort does not require random access and works well with linked lists

C Because quicksort is faster on linked lists

D Because quicksort cannot be implemented on linked lists

💡 Hint

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

Merge sort works well with linked lists because it only requires sequential access, unlike quicksort which needs random access.

🔧 Debug

advanced

Identify the Bug in Merge Sort Implementation

What error will this code cause when sorting a linked list using merge sort?

Code snippet:
struct Node* mergeSort(struct Node* head) { if (head == NULL || head->next == NULL) { return head; } struct Node* middle = getMiddle(head); struct Node* nextOfMiddle = middle->next; middle->next = NULL; struct Node* left = mergeSort(head); struct Node* right = mergeSort(nextOfMiddle); struct Node* sortedList = sortedMerge(left, right); return sortedList; } // getMiddle returns the middle node of the list // sortedMerge merges two sorted lists

A Segmentation fault due to incorrect middle node calculation

B Infinite recursion because base case is missing

C No error, code runs correctly

D Memory leak due to not freeing nodes

💡 Hint

Check how getMiddle is implemented and what happens if middle is NULL.

If getMiddle returns NULL or incorrect node, accessing middle->next causes segmentation fault.

📝 Syntax

advanced

Correct the Syntax Error in Merge Function

Which option correctly fixes the syntax error in this merge function snippet?

Code snippet:
struct Node* sortedMerge(struct Node* a, struct Node* b) { struct Node* result = NULL; if (a == NULL) return b else if (b == NULL) return a; if (a->data <= b->data) { result = a; result->next = sortedMerge(a->next, b); } else { result = b; result->next = sortedMerge(a, b->next); } return result; }

A Replace 'result = a;' with 'result == a;'

B Change 'else if' to 'if' in second condition

C Add semicolon after 'return b' line

D Remove 'return result;' line

💡 Hint

Check missing punctuation after return statements.

The line 'return b' is missing a semicolon, causing a syntax error.

🚀 Application

expert

Time Complexity of Merge Sort on Linked List

What is the time complexity of merge sort when sorting a linked list with n nodes?

A O(n^2)

B O(log n)

C O(n)

D O(n log n)

💡 Hint

Consider how merge sort divides and merges the list.

Merge sort divides the list into halves log n times and merges n nodes each time, resulting in O(n log n).

Practice

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

easy

A. Merge sort does not require random access, which suits linked lists well.

B. Quicksort uses less memory than merge sort for linked lists.

C. Merge sort is faster than quicksort on arrays.

D. Quicksort is stable while merge sort is not.

Solution

1. Step 1: Understand linked list access

   Linked lists do not support fast random access, unlike arrays.

2. Step 2: Compare sorting algorithms

   Merge sort works well with sequential access, while quicksort relies on random access for efficiency.

3. Final Answer:

   Merge sort does not require random access, which suits linked lists well. -> Option A

4. Quick Check:

   Linked list + merge sort = no random access needed [OK]

Hint: Merge sort fits linked lists due to sequential access [OK]

Common Mistakes:

• Thinking quicksort is always better
• Assuming merge sort needs random access
• Confusing stability of sorting algorithms

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

easy

A. Split by dividing the node values by 2.

B. Use two pointers: slow moves 1 step, fast moves 2 steps; slow marks mid.

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

D. Use recursion without splitting the list.

Solution

1. Step 1: Identify splitting technique

   The fast and slow pointer method finds the middle node efficiently.

2. Step 2: Understand pointer movement

   Slow pointer moves one node at a time, fast pointer moves two nodes; when fast reaches end, slow is at mid.

3. Final Answer:

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

4. Quick Check:

   Fast/slow pointers split linked list [OK]

Hint: Use fast/slow pointers to find middle node [OK]

Common Mistakes:

• Trying to split by node values
• Using only one pointer to split
• Not stopping fast pointer correctly

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 list into halves recursively

   Split into (4 -> 2) and (1 -> 3), then further split until single nodes.

2. Step 2: Merge sorted halves

   Merge nodes in order: 1, 2, 3, 4 to get sorted list.

3. Final Answer:

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

4. Quick Check:

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

Hint: Merge sort outputs ascending sorted list [OK]

Common Mistakes:

• Confusing merge order
• Not splitting correctly
• Assuming original order remains

4. In the following C code snippet for merge sort on linked list, what is the error?

Node* mergeSort(Node* head) {
  if (!head || !head->next) return head;
  Node* slow = head;
  Node* fast = head;
  while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
  }
  Node* mid = slow->next;
  slow->next = NULL;
  Node* left = mergeSort(head);
  Node* right = mergeSort(mid);
  return merge(left, right);
}

medium

A. The base case should check only for head->next, not head.

B. Slow pointer should move two steps each iteration.

C. Fast pointer should start at head->next, not head.

D. The function should not split the list.

Solution

1. Step 1: Analyze pointer initialization

   Fast pointer should start at head->next to correctly find middle for even nodes.

2. Step 2: Understand pointer movement impact

   Starting fast at head skips the first node, causing incorrect mid calculation.

3. Final Answer:

   Fast pointer should start at head->next, not head. -> Option C

4. Quick Check:

   Fast pointer start affects mid node [OK]

Hint: Start fast pointer at head->next for correct mid [OK]

Common Mistakes:

• Starting fast at head
• Moving slow pointer incorrectly
• Ignoring base case conditions

5. You have a linked list with duplicate values: 5 -> 3 -> 8 -> 5 -> 2 -> NULL. After applying merge sort, which of the following is the correct sorted list?

hard

A. 2 -> 3 -> 5 -> 5 -> 8 -> NULL

B. 5 -> 3 -> 8 -> 5 -> 2 -> NULL

C. 2 -> 3 -> 8 -> 5 -> 5 -> NULL

D. 3 -> 2 -> 5 -> 5 -> 8 -> NULL

Solution

1. Step 1: Understand merge sort stability

   Merge sort preserves order of equal elements, so duplicates stay in relative order.

2. Step 2: Sort values ascending

   Sorted order is 2, 3, 5, 5, 8 with duplicates adjacent.

3. Final Answer:

   2 -> 3 -> 5 -> 5 -> 8 -> NULL -> Option A

4. Quick Check:

   Sorted with duplicates preserved = 2,3,5,5,8 [OK]

Hint: Merge sort keeps duplicates in order [OK]

Common Mistakes:

• Assuming duplicates get removed
• Sorting duplicates incorrectly
• Mixing order of duplicates