Sort a Linked List using Merge Sort

Introduction

Sorting a linked list efficiently is a common problem in data structures. Unlike arrays, linked lists do not allow direct access to elements, so algorithms like quicksort are not ideal.

Merge Sort is the best choice for linked lists because:

• It does not require random access

• It works efficiently with node-based structures

Problem Statement

Given the head of a linked list:

• Sort the list in ascending order

• Return the sorted linked list

Example

Input:

10 -> 30 -> 20 -> 40 -> 60 -> 50

Output:

10 -> 20 -> 30 -> 40 -> 50 -> 60

Solution Code

class Solution:
    def mergeSort(self, head):
        if not head or not head.next:
            return head
        
        mid = self.getMiddle(head)
        next_to_mid = mid.next
        mid.next = None
        
        left = self.mergeSort(head)
        right = self.mergeSort(next_to_mid)
        
        return self.merge(left, right)
    
    def getMiddle(self, head):
        slow = head
        fast = head.next
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        return slow
    
    def merge(self, left, right):
        dummy = Node(0)
        tail = dummy
        
        while left and right:
            if left.data <= right.data:
                tail.next = left
                left = left.next
            else:
                tail.next = right
                right = right.next
            tail = tail.next
        
        if left:
            tail.next = left
        else:
            tail.next = right
        
        return dummy.next

Approach Used: Merge Sort on Linked List

Idea

We divide the linked list into two halves, sort them recursively, and then merge the sorted halves.

How It Works

Step 1: Find Middle

• Use slow and fast pointers

• Split the list into two halves

Step 2: Divide

• Recursively apply merge sort on both halves

Step 3: Merge

• Merge the two sorted lists into one sorted list

Why This Approach Was Chosen

• Works efficiently for linked lists

• Does not require extra random access

• Better than other sorting algorithms for linked lists

Alternative Approaches

• Convert to array => sort => convert back
  Uses extra space

• Bubble Sort / Insertion Sort
   O(n²) time complexity

Why Merge Sort?
Because it gives optimal performance for linked lists

Time and Space Complexity

• Time Complexity: O(n log n)

• Space Complexity: O(log n) (recursion stack)

Observation

• Splitting is done using slow-fast pointer

• Merging is similar to merging two sorted lists

• Linked list structure makes merge efficient

Edge Cases

• Empty list = return null

• Single node = already sorted

• Duplicate values = handled correctly

Conclusion

Merge Sort is the most efficient way to sort a linked list. By dividing the list and merging sorted parts, we achieve optimal performance while working within the constraints of linked list structure.