Merge Sort for Linked List

When I first started working with linked lists, most problems were about traversal or simple modifications like insertion or reversal. But sorting a linked list felt different, especially when I was asked to use merge sort.

To understand this properly, I first went back and revised two things:

What exactly a linked list is
How merge sort works

Once those were clear, applying merge sort to a linked list started making sense.

Understanding Linked List
A linked list is a collection of nodes where each node contains:

Data
A reference (or pointer) to the next node

Unlike arrays:
Elements are not stored in contiguous memory
There is no direct indexing like arr[i]

Example:

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

Here, each element points to the next one.
Because of this structure:

Traversal is sequential
Random access is not possible
But insertion and deletion are easier**

Why Sorting is Different in Linked Lists

In arrays:

We can access any element directly
Sorting algorithms like quicksort or heap sort work efficiently

In linked lists:
We cannot jump to the middle directly
Swapping elements is not efficient

So we need a sorting algorithm that:

Works well with sequential access
Does not rely on indexing

This is where merge sort fits perfectly.

Quick Brush Up on Merge Sort

Merge sort is a divide-and-conquer algorithm.

Steps:

Divide the array into two halves
Recursively sort both halves
Merge the sorted halves

Example:

[10, 30, 20, 50]

Split:
[10, 30] and [20, 50]

Sort:
[10, 30] and [20, 50]

Merge:
[10, 20, 30, 50]

Why Merge Sort is Ideal for Linked Lists

Merge sort works well with linked lists because:

Splitting can be done using slow and fast pointers,Merging does not require extra space for shifting elements and We only change pointers, not actual data

So it naturally fits the linked list structure.

How I Applied Merge Sort to Linked List

The idea is the same as arrays, but implementation is different.

Approach

Find the middle of the linked list
Split the list into two halves
Recursively sort both halves
Merge the two sorted lists

Finding the Middle

We use two pointers:

slow → moves one step
fast → moves two steps

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

Merging Two Sorted Lists

This is similar to merging in merge sort:
Compare nodes from both lists
Attach the smaller one
Move forward

Algorithm

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


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

        # Find middle
        mid = self.getMiddle(head)
        next_to_mid = mid.next
        mid.next = None

        # Sort left and right
        left = self.mergeSort(head)
        right = self.mergeSort(next_to_mid)

        # Merge
        sorted_list = self.merge(left, right)
        return sorted_list

    def getMiddle(self, head):
        if head is None:
            return head

        slow = head
        fast = head

        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next

        return slow

    def merge(self, left, right):
        if left is None:
            return right
        if right is None:
            return left

        if left.data <= right.data:
            result = left
            result.next = self.merge(left.next, right)
        else:
            result = right
            result.next = self.merge(left, right.next)

        return result