Merge sort on a linked list

Merge Sort on a Linked List

1. Sorting a linked list is a common problem in data structures. Unlike arrays, linked lists do not support direct indexing, so some sorting algorithms are not efficient.

2. Merge Sort is the most suitable algorithm for linked lists because it does not require random access and works efficiently with pointers
   .

Understanding the Problem

Given a linked list like:
4 --> 2 --> 1 --> 3

We need to sort it into:
1 --> 2 --> 3 --> 4

Why Use Merge Sort for Linked Lists

Merge Sort is preferred because:

It works efficiently with linked lists
I

1. t does not require extra space for shifting elements
2. It has a time complexity of O(n log n)
3. It uses the natural structure of linked lists for splitting and merging

Approach Overview

The algorithm follows three main steps:

Divide the list into two halves
Recursively sort each half
Merge the two sorted halves

Code Structure
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Solution:
    def mergeSort(self, head):
        if not head or not head.next:
            return head

        mid = self.getMiddle(head)
        right = mid.next
        mid.next = None

        left = self.mergeSort(head)
        right = self.mergeSort(right)

        return self.merge(left, right)

**Step-by-Step Explanation

1. Base Case** if not head or not head.next: return head

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

2. Find the Middle of the List
mid = self.getMiddle(head)

We split the list into two halves using the middle node.

Finding the Middle
def getMiddle(self, head):
slow, fast = head, head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
return slow

This uses the slow and fast pointer technique:

slow moves one step at a time
fast moves two steps at a time

When fast reaches the end, slow will be at the middle.

3. Split the List

right = mid.next
mid.next = None
The list is divided into two halves
Left half starts from head
Right half starts from mid.next

4. Recursively Sort Both Halves

left = self.mergeSort(head)
right = self.mergeSort(right)

Each half is sorted independently using the same function.

5. Merge the Sorted Lists

return self.merge(left, right)

Now we combine the two sorted halves into one sorted list.

Merge Function
def merge(self, a, b):
if not a: return b
if not b: return a
if a.data <= b.data:
a.next = self.merge(a.next, b)
return a
else:
b.next = self.merge(a, b.next)
return b
How Merging Works
Compare the first nodes of both lists
Pick the smaller one
Recursively merge the remaining nodes

This builds a sorted list step by step.

Example Walkthrough

Input:

4 -> 2 -> 1 -> 3

Steps:

Split into: 4 --> 2 and 1 --> 3
Further split into individual nodes
Merge: 4 and 2 becomes 2 --> 4
Merge: 1 and 3 becomes 1 --> 3
Final merge: 2 --> 4 and 1 --> 3 becomes 1 --> 2 --> 3 --> 4
Key Insight

The main idea is to repeatedly divide the list until each part contains a single element, then merge them back in sorted order.

Time and Space Complexity

Time complexity is O(n log n) because:

The list is divided into halves repeatedly
Each merge operation takes linear time

Space complexity is O(log n) due to recursion.