Sort Linked List - Merge Sort

Sort a linked list in ascending order using merge sort with O(n log n) time complexity

Linked List

Phase

Current operation

Slow Ptr

Finds middle

Fast Ptr

Moves 2x speed

Depth

Recursion level

Click "Step" or "Play" to start sorting the linked list

Unsorted

Finding Mid

Split Point

Comparing

Selected

Sorted

▼ slow - moves 1 step

▼ fast - moves 2 steps

Python Code - Merge Sort (Linked List)

                def sortList(head):
            
                    if not head or not head.next:
            
                        return head
            
                    mid = getMid(head)
            
                    left = head
            
                    right = mid.next
            
                    mid.next = None # Split the list
            
                    left_sorted = sortList(left)
            
                    right_sorted = sortList(right)
            
                    return merge(left_sorted, right_sorted)
            
                def getMid(head): # Slow/Fast pointers
            
                    slow, fast = head, head.next
            
                    while fast and fast.next:
            
                        slow = slow.next
            
                        fast = fast.next.next
            
                    return slow
            
                def merge(l1, l2): # Merge two sorted lists
            
                    dummy = ListNode()
            
                    tail = dummy
            
                    while l1 and l2:
            
                        if l1.val < l2.val:
            
                            tail.next = l1; l1 = l1.next
            
                        else:
            
                            tail.next = l2; l2 = l2.next
            
                        tail = tail.next
            
                    tail.next = l1 or l2
            
                    return dummy.next

Complexity Analysis

Time Complexity O(n log n) Space Complexity O(log n)

Time Complexity: O(n log n)

Breakdown

Find middle (slow/fast): O(n) per level
Merge two sorted lists: O(n) per level
Recursion depth: O(log n) levels
Total: O(log n) levels × O(n) work = O(n log n)

T(n) = 2T(n/2) + O(n) → O(n log n) by Master theorem

Mathematical Intuition

Merge sort divides the list in half recursively until single nodes remain, then merges sorted halves bottom-up. Each level of recursion processes all n elements exactly once (during merging), and there are log n levels. The slow/fast pointer technique finds the midpoint in O(n) without random access.

Key Insight

Unlike quicksort (O(n²) worst case), merge sort guarantees O(n log n) for all inputs—making it the preferred choice for linked lists.

Space Complexity: O(log n)

Breakdown

Recursion stack depth: O(log n)
Each stack frame: O(1) pointers
No auxiliary array for merging
Merging is done by relinking pointers

S(n) = O(log n) — recursion stack only

Mathematical Intuition

Array merge sort requires O(n) auxiliary space for merging. Linked list merge sort achieves O(1) merge space because we can rearrange pointers without copying elements. The only space cost is the recursion stack, which has depth log n due to balanced splitting.

Key Insight

Bottom-up iterative merge sort eliminates the recursion stack entirely, achieving O(1) auxiliary space for linked lists.