Sort a Linked List Using Merge Sort in DSA C - Build from Scratch

Sort a Linked List Using Merge Sort

📖 Scenario: You are working on a program that manages a list of tasks. Each task has a priority number. To organize tasks efficiently, you want to sort the tasks by their priority using a linked list.

🎯 Goal: Build a program that creates a linked list of tasks with priorities, then sorts this linked list using the merge sort algorithm.

📋 What You'll Learn

Create a linked list with given task priorities

Implement a function to split the linked list into halves

Implement a function to merge two sorted linked lists

Implement merge sort to sort the linked list

Print the sorted linked list priorities

💡 Why This Matters

🌍 Real World

Sorting linked lists is useful in many applications like task scheduling, managing priority queues, and organizing data streams where dynamic memory allocation is preferred.

💼 Career

Understanding linked list sorting algorithms like merge sort is important for software engineering roles that involve data structure optimization and memory-efficient programming.

1

Create the Linked List

Create a linked list with nodes containing these exact priority values in order: 4, 2, 5, 1, 3. Use the struct Node with an int priority and a Node* next. Create a pointer head pointing to the first node.

DSA C

#include 
#include 

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

int main() {
    // Create linked list nodes with priorities 4, 2, 5, 1, 3
    // Your code here
    return 0;
}

Hint

Use malloc to create each node. Link them by setting the next pointer of each node to the next node.

2

Add a Function to Split the List

Add a function called splitList that takes a struct Node* called source and splits it into two halves. It should set two pointers frontRef and backRef to the front and back halves respectively. Use the fast and slow pointer method.

DSA C

#include 
#include 

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

// Add the splitList function here
// Your code here

int main() {
    struct Node* head = malloc(sizeof(struct Node));
    head->priority = 4;
    head->next = malloc(sizeof(struct Node));
    head->next->priority = 2;
    head->next->next = malloc(sizeof(struct Node));
    head->next->next->priority = 5;
    head->next->next->next = malloc(sizeof(struct Node));
    head->next->next->next->priority = 1;
    head->next->next->next->next = malloc(sizeof(struct Node));
    head->next->next->next->next->priority = 3;
    head->next->next->next->next->next = NULL;
    return 0;
}

Hint

Use two pointers: slow moves one step, fast moves two steps. When fast reaches the end, slow is at the middle.

3

Add Merge and Merge Sort Functions

Add two functions: mergeSortedLists that merges two sorted linked lists into one sorted list, and mergeSort that sorts a linked list using merge sort recursively. Use the splitList function to divide the list.

DSA C

#include 
#include 

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

void splitList(struct Node* source, struct Node** frontRef, struct Node** backRef) {
    struct Node* slow;
    struct Node* fast;
    if (source == NULL || source->next == NULL) {
        *frontRef = source;
        *backRef = NULL;
        return;
    }
    slow = source;
    fast = source->next;
    while (fast != NULL) {
        fast = fast->next;
        if (fast != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
    }
    *frontRef = source;
    *backRef = slow->next;
    slow->next = NULL;
}

// Add mergeSortedLists and mergeSort functions here
// Your code here

int main() {
    struct Node* head = malloc(sizeof(struct Node));
    head->priority = 4;
    head->next = malloc(sizeof(struct Node));
    head->next->priority = 2;
    head->next->next = malloc(sizeof(struct Node));
    head->next->next->priority = 5;
    head->next->next->next = malloc(sizeof(struct Node));
    head->next->next->next->priority = 1;
    head->next->next->next->next = malloc(sizeof(struct Node));
    head->next->next->next->next->priority = 3;
    head->next->next->next->next->next = NULL;
    return 0;
}

Hint

Use recursion in mergeSort. Base case is when list is empty or has one node. Use mergeSortedLists to combine sorted halves.

4

Print the Sorted Linked List

Add a function called printList that takes struct Node* head and prints the priorities in order separated by spaces. Then call printList(head) in main after sorting.

DSA C

Hint

Traverse the list from head to NULL, printing each priority followed by a space.

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