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).