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 contact management app. The contacts are stored in a linked list by the order they were added. Now, you want to sort the contacts alphabetically by their names using an efficient method.

🎯 Goal: Build a program that sorts a singly linked list of contact names using the merge sort algorithm.

📋 What You'll Learn

Create a singly linked list with given contact names

Implement a function to split the linked list into halves

Implement a function to merge two sorted linked lists

Implement the merge sort function for the linked list

Print the sorted linked list

💡 Why This Matters

🌍 Real World

Sorting linked lists is useful in applications like contact managers, music playlists, or any system that stores data in linked lists and needs sorted output.

💼 Career

Understanding linked list sorting with merge sort is important for software engineers working on data structures, optimizing algorithms, and handling dynamic data efficiently.

1

Create the Linked List

Create a singly linked list with the exact contact names in this order: "John", "Alice", "Bob", "Diana", "Charlie". Use the struct Node with string name and Node* next. Create a pointer head pointing to the first node.

DSA C++

#include 
#include 
using namespace std;

struct Node {
    string name;
    Node* next;
    Node(string n) : name(n), next(nullptr) {}
};

int main() {
    // Create nodes and link them in order: John -> Alice -> Bob -> Diana -> Charlie
    // Your code here
    return 0;
}

Hint

Start by creating the first node with new Node("John"). Then link each next node using head->next and so on.

2

Add a Function to Split the List

Add a function void splitList(Node* source, Node** frontRef, Node** backRef) that splits the linked list source into two halves. Use the slow and fast pointer approach. The first half should be assigned to *frontRef and the second half to *backRef.

DSA C++

#include 
#include 
using namespace std;

struct Node {
    string name;
    Node* next;
    Node(string n) : name(n), next(nullptr) {}
};

// Add the splitList function here

int main() {
    Node* head = new Node("John");
    head->next = new Node("Alice");
    head->next->next = new Node("Bob");
    head->next->next->next = new Node("Diana");
    head->next->next->next->next = new Node("Charlie");
    // Your code here
    return 0;
}

Hint

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

3

Implement Merge and MergeSort Functions

Add a function Node* sortedMerge(Node* a, Node* b) that merges two sorted linked lists a and b into one sorted list by name. Then add a recursive function void mergeSort(Node** headRef) that sorts the linked list using merge sort. Use splitList and sortedMerge inside mergeSort.

DSA C++

#include 
#include 
using namespace std;

struct Node {
    string name;
    Node* next;
    Node(string n) : name(n), next(nullptr) {}
};

// Add sortedMerge function here

// Add mergeSort function here

int main() {
    Node* head = new Node("John");
    head->next = new Node("Alice");
    head->next->next = new Node("Bob");
    head->next->next->next = new Node("Diana");
    head->next->next->next->next = new Node("Charlie");
    // Your code here
    return 0;
}

Hint

Use recursion in mergeSort to sort each half, then merge them with sortedMerge.

4

Sort and Print the Linked List

Call mergeSort(&head) in main to sort the linked list. Then print the sorted list by traversing from head, printing each name followed by -> , ending with null.

DSA C++

#include 
#include 
using namespace std;

struct Node {
    string name;
    Node* next;
    Node(string n) : name(n), next(nullptr) {}
};

void splitList(Node* source, Node** frontRef, Node** backRef) {
    Node* slow = source;
    Node* fast = source->next;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
    *frontRef = source;
    *backRef = slow->next;
    slow->next = nullptr;
}

Node* sortedMerge(Node* a, Node* b) {
    if (a == nullptr) return b;
    if (b == nullptr) return a;
    Node* result = nullptr;
    if (a->name name) {
        result = a;
        result->next = sortedMerge(a->next, b);
    } else {
        result = b;
        result->next = sortedMerge(a, b->next);
    }
    return result;
}

void mergeSort(Node** headRef) {
    Node* head = *headRef;
    if (head == nullptr || head->next == nullptr) {
        return;
    }
    Node* a;
    Node* b;
    splitList(head, &a, &b);
    mergeSort(&a);
    mergeSort(&b);
    *headRef = sortedMerge(a, b);
}

int main() {
    Node* head = new Node("John");
    head->next = new Node("Alice");
    head->next->next = new Node("Bob");
    head->next->next->next = new Node("Diana");
    head->next->next->next->next = new Node("Charlie");

    // Sort the linked list
    // Print the sorted linked list
    // Your code here
    return 0;
}

Hint

Call mergeSort(&head) to sort. Then use a while loop to print each node's name followed by -> . End with null.

Practice

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

easy

A. It only works for arrays, not linked lists.

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

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

D. It requires the list to be converted to an array first.

Solution

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

   Merge sort divides the list and merges sorted halves, 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 need extra arrays, so it uses less extra space.

3. Final Answer:

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

4. Quick Check:

   Merge sort = O(n log n) + low extra space [OK]

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

Common Mistakes:

• Thinking merge sort uses extra arrays for linked lists
• Confusing merge sort with bubble sort time complexity
• Assuming linked lists must be converted to arrays first

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

easy

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

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

C. Split by dividing the node values by 2.

D. Use recursion without splitting the list.

Solution

1. Step 1: Identify the standard splitting technique

   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 is less efficient; dividing values is meaningless; recursion needs splitting first.

3. Final Answer:

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

4. Quick Check:

   Two-pointer split = Use two pointers: slow moves 1 step, fast moves 2 steps; slow marks middle. [OK]

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

Common Mistakes:

• Trying to split by counting nodes first
• Splitting based on node values instead of positions
• Not splitting before recursive calls

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

medium

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

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

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

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

Solution

1. Step 1: Break list into halves and sort recursively

   Split into (4 -> 2) and (1 -> 3), sort each: (2 -> 4), (1 -> 3).

2. Step 2: Merge sorted halves

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

3. Final Answer:

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

4. Quick Check:

   Sorted ascending = 1 -> 2 -> 3 -> 4 -> null [OK]

Hint: Merge sort always returns ascending sorted list [OK]

Common Mistakes:

• Confusing merge order and producing descending list
• Not fully sorting both halves before merging
• Merging without comparing node values

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

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 = nullptr;
  Node* left = mergeSort(head);
  Node* right = mergeSort(mid);
  return merge(left, right);
}

medium

A. The base case should check only if head is nullptr.

B. Slow pointer should move twice as fast as fast pointer.

C. The merge function is called with wrong arguments.

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

Solution

1. Step 1: Analyze pointer initialization

   Fast pointer starting at head causes incorrect middle for even length lists.

2. Step 2: Correct initialization for proper middle detection

   Fast should start at head->next to ensure slow points to middle correctly.

3. Final Answer:

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

4. Quick Check:

   Fast pointer start = head->next [OK]

Hint: Start fast pointer at head->next to find middle correctly [OK]

Common Mistakes:

• Starting fast pointer at head causing wrong split
• Confusing slow and fast pointer speeds
• Ignoring base case for single node

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

hard

A. 3 -> 3 -> 5 -> 5 -> 8 -> null

B. 5 -> 3 -> 8 -> 3 -> 5 -> null

C. 8 -> 5 -> 5 -> 3 -> 3 -> null

D. 3 -> 5 -> 8 -> 3 -> 5 -> null

Solution

1. Step 1: Understand merge sort handles duplicates by comparing values

   During merge, nodes with equal values are placed in order preserving duplicates.

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

   Sorted order is ascending: 3, 3, 5, 5, 8.

3. Final Answer:

   3 -> 3 -> 5 -> 5 -> 8 -> null -> Option A

4. Quick Check:

   Duplicates preserved and sorted ascending [OK]

Hint: Merge sort keeps duplicates and sorts ascending [OK]

Common Mistakes:

• Assuming duplicates are removed
• Sorting in descending order by mistake
• Not merging duplicates correctly