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

Sort a Linked List Using Merge Sort

📖 Scenario: You are working on a contact list app. The contacts are stored in a linked list, but they are not sorted by name. You want to sort the contacts alphabetically to make searching easier.

🎯 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 merge sort to sort the linked list by contact names

Print the sorted linked list

💡 Why This Matters

🌍 Real World

Sorting linked lists is useful in applications like contact management, where data is stored in linked lists and needs to be ordered for quick search and display.

💼 Career

Understanding linked list sorting algorithms like merge sort is important for software engineers working with low-level data structures, memory-efficient algorithms, and interview coding challenges.

1

Create the Linked List

Create a class called Node with attributes name and next. Then create a linked list with these exact contact names in order: 'John', 'Alice', 'Bob', 'Diana', 'Charlie'. Store the head node in a variable called head.

DSA Python

# Define Node class and create linked list with given names
# Your code here

Hint

Define the Node class first. Then link nodes by setting the next attribute.

2

Add a Function to Split the List

Add a function called split_list that takes head of a linked list and returns two heads: left and right. Use the slow and fast pointer technique to find the middle and split the list into two halves.

DSA Python

class Node:
    def __init__(self, name):
        self.name = name
        self.next = None

head = Node('John')
head.next = Node('Alice')
head.next.next = Node('Bob')
head.next.next.next = Node('Diana')
head.next.next.next.next = Node('Charlie')

# Define split_list function below
# Your code here

Hint

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

3

Add Merge and Merge Sort Functions

Add a function called merge_sorted_lists that takes two sorted linked lists left and right and merges them into one sorted list by name. Then add a function called merge_sort that takes head of a linked list and returns the sorted linked list using merge sort. Use split_list and merge_sorted_lists inside merge_sort.

DSA Python

class Node:
    def __init__(self, name):
        self.name = name
        self.next = None

head = Node('John')
head.next = Node('Alice')
head.next.next = Node('Bob')
head.next.next.next = Node('Diana')
head.next.next.next.next = Node('Charlie')

def split_list(head):
    if head is None or head.next is None:
        return head, None
    slow = head
    fast = head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    left = head
    right = slow.next
    slow.next = None
    return left, right

# Define merge_sorted_lists and merge_sort functions below
# Your code here

Hint

Merge two sorted lists by comparing name values. Use recursion for merge sort.

4

Print the Sorted Linked List

Use the merge_sort function to sort the linked list starting at head. Then print the sorted list names in order separated by -> and ending with null.

DSA Python

class Node:
    def __init__(self, name):
        self.name = name
        self.next = None

head = Node('John')
head.next = Node('Alice')
head.next.next = Node('Bob')
head.next.next.next = Node('Diana')
head.next.next.next.next = Node('Charlie')

def split_list(head):
    if head is None or head.next is None:
        return head, None
    slow = head
    fast = head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    left = head
    right = slow.next
    slow.next = None
    return left, right

def merge_sorted_lists(left, right):
    if left is None:
        return right
    if right is None:
        return left
    if left.name <= right.name:
        result = left
        result.next = merge_sorted_lists(left.next, right)
    else:
        result = right
        result.next = merge_sorted_lists(left, right.next)
    return result

def merge_sort(head):
    if head is None or head.next is None:
        return head
    left, right = split_list(head)
    left = merge_sort(left)
    right = merge_sort(right)
    return merge_sorted_lists(left, right)

# Sort the linked list and print the sorted names
# Your code here

Hint

Call merge_sort(head) to get the sorted list head. Then loop through the list to collect names and print them joined by -> ending with null.

Practice

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

easy

A. Quicksort is unstable, but merge sort is always unstable.

B. Merge sort uses less memory than quicksort for linked lists.

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

D. Merge sort sorts linked lists in-place without extra space.

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 by splitting and merging, which only needs sequential access, making it suitable for linked lists.

3. Final Answer:

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

4. Quick Check:

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

Hint: Merge sort fits linked lists because it uses sequential access [OK]

Common Mistakes:

• Thinking quicksort is better for linked lists
• Believing merge sort sorts in-place without extra space
• Confusing stability properties of sorting algorithms

2. Which of the following is the correct base case condition in a recursive merge sort function for a linked list?

easy

A. if head is None and head.next is None: return None

B. if head is None or head.next is None: return None

C. if head.next is None: return None

D. if head is None or head.next is None: return head

Solution

1. Step 1: Identify base case for recursion

   When the list is empty or has one node, it is already sorted.

2. Step 2: Correct base case condition

   Check if head is None (empty list) or head.next is None (single node), then return head.

3. Final Answer:

   if head is None or head.next is None: return head -> Option D

4. Quick Check:

   Base case returns head when list size ≤ 1 [OK]

Hint: Base case returns head if list empty or single node [OK]

Common Mistakes:

• Returning None instead of head for single node
• Using 'and' instead of 'or' in condition
• Missing base case leading to infinite recursion

3. What will be the output linked list after applying merge sort on the following linked list?

4 -> 2 -> 1 -> 3 -> None

medium

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

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

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

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

Solution

1. Step 1: Split the list into halves

   Split into (4 -> 2) and (1 -> 3).

2. Step 2: Recursively sort and merge

   Sort (4 -> 2) to (2 -> 4), sort (1 -> 3) to (1 -> 3), then merge to (1 -> 2 -> 3 -> 4).

3. Final Answer:

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

4. Quick Check:

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

Hint: Merge sort outputs sorted list in ascending order [OK]

Common Mistakes:

• Confusing merge order and producing unsorted output
• Not splitting list correctly
• Merging without sorting halves first

4. Given this merge function snippet for linked lists, what is the bug?

def merge(left, right):
    if not left:
        return right
    if not right:
        return left
    if left.val < right.val:
        result = left
        result.next = merge(left.next, right)
    else:
        result = right
        result.next = merge(left, right.next)
    return result

medium

A. The comparison should be <= instead of < to maintain stability.

B. No bug; function correctly merges two sorted lists.

C. The function does not handle empty lists properly.

D. The function should return None at the end instead of result.

Solution

1. Step 1: Analyze base cases

   Returns right if left is None, and left if right is None, correctly handling empty lists.

2. Step 2: Check recursive merge logic

   Compares values, assigns result, and recursively merges remaining nodes correctly.

3. Final Answer:

   No bug; function correctly merges two sorted lists. -> Option B

4. Quick Check:

   Merge function logic is correct and complete [OK]

Hint: Check base cases and recursion carefully for merge correctness [OK]

Common Mistakes:

• Thinking <= is required for stability (not always needed)
• Missing base case returns
• Returning None instead of merged list

5. You have a linked list with nodes:

5 -> 3 -> 8 -> 2 -> 7 -> None

After applying merge sort, what will be the final linked list? Also, what is the time complexity of merge sort on this linked list?

hard

A. 2 -> 3 -> 5 -> 7 -> 8 -> None; Time complexity: O(n log n)

B. 2 -> 3 -> 5 -> 7 -> 8 -> None; Time complexity: O(n^2)

C. 5 -> 3 -> 8 -> 2 -> 7 -> None; Time complexity: O(n log n)

D. 3 -> 2 -> 5 -> 7 -> 8 -> None; Time complexity: O(n)

Solution

1. Step 1: Sort the linked list nodes

   Sorted order is 2 -> 3 -> 5 -> 7 -> 8.

2. Step 2: Understand merge sort time complexity

   Merge sort divides list and merges in O(n log n) time for n nodes.

3. Final Answer:

   2 -> 3 -> 5 -> 7 -> 8 -> None; Time complexity: O(n log n) -> Option A

4. Quick Check:

   Sorted list + merge sort time = O(n log n) [OK]

Hint: Merge sort always sorts in O(n log n) time [OK]

Common Mistakes:

• Confusing time complexity with O(n^2)
• Not sorting nodes correctly
• Assuming merge sort is O(n)