L26. Sort a Linked List | Merge Sort and Brute Force

Sorting a linked list is a fundamental algorithmic challenge where you are given the head of a singly linked list containing unsorted integers, and your task is to rearrange the nodes so that the values are in non-decreasing order, ultimately returning the head of the updated list. This chapter explores both the extreme naive (brute force) approach and the optimal in-place Merge Sort strategy, complete with time-space complexity analyses and edge-case handling.

1. Why Do We Need This? (Problem Statement & Status Quo)

When dealing with arrays, sorting is straightforward because elements reside in contiguous memory locations, allowing random access. However, linked lists consist of nodes scattered across memory, connected solely by pointers.

• Input: The head pointer of an unsorted singly linked list.
• Output: The head pointer of the same linked list, but with its node values fully sorted in ascending order.
• The Core Challenge: How can we achieve efficient sorting ($O(N \log N)$ time) without violating the dynamic memory constraints of linked lists, particularly targeting $O(1)$ auxiliary space?

2. The Naive (Brute Force) Approach

The most intuitive, albeit suboptimal, way to solve this problem is to extract all the elements out of the linked list, place them into an auxiliary data structure (like an array or list), sort them using any standard sorting algorithm, and then overwrite the linked list values.

Step-by-Step Execution of the Naive Approach

1. Extraction: Initialize a temporary pointer (temp) at the head. Traverse the list until temp reaches null, appending each node's data into a dynamic array.
2. Sorting: Apply a standard sorting algorithm (such as Merge Sort or Quick Sort) directly on the array.
3. Re-insertion (Overwriting): Reset temp to the head and an index variable i to 0. Traverse the linked list a second time, replacing temp.data with array[i], then advance both temp and i.

Naive Algorithm Pseudo-Code

def sortListBruteForce(head):
    if not head:
        return head
    
    # Step 1: Extract elements into an array
    arr = []
    temp = head
    while temp is not None:
        arr.append(temp.data)
        temp = temp.next
        
    # Step 2: Sort the array
    arr.sort() # O(N log N)
    
    # Step 3: Overwrite linked list data
    temp = head
    i = 0
    while temp is not None:
        temp.data = arr[i]
        i += 1
        temp = temp.next
        
    return head

Complexity Analysis of Brute Force

• Time Complexity: $O(N) \text{ (extraction)} + O(N \log N) \text{ (sorting)} + O(N) \text{ (re-insertion)} = O(N \log N)$
• Space Complexity: $O(N)$ auxiliary space required to store all linked list elements in an external array.

3. The Interviewer's Constraint: Optimizing Space

An auxiliary space complexity of $O(N)$ is generally unacceptable to an interviewer when sorting linked lists.

• The Hint: Since external storage is forbidden, any efficient sorting algorithm must manipulate the nodes, pointers, and values in-place within the linked list structure.
• Candidate Algorithms: Quick Sort and Merge Sort are the leading $O(N \log N)$ sorting algorithms. While Quick Sort can be implemented on linked lists, Merge Sort is significantly cleaner and easier to reason about because it does not require complex pointer pivoting.

4. Core Mental Model: Merge Sort on Linked Lists

Merge Sort operates on a divide-and-conquer paradigm. In the context of linked lists, the workflow mimics array-based merge sort with a few structural adjustments.

Real-Life Analogy: Splitting and Merging a Deck of Cards

Imagine sorting a thick, unsorted deck of cards. Instead of trying to sort the whole deck at once, you cut the deck squarely in half. You hand the left stack to one friend and the right stack to another. They each split their stacks in half recursively until everyone holds a single card (which is inherently sorted). Finally, you pair up the sorted piles, comparing the top cards one by one to weave them back into a single, perfectly ordered deck.

High-Level Recursive Flow

5. Step-by-Step Evolution of Merge Sort Code

Implementing Merge Sort on a linked list requires three foundational helper routines:

1. Base Case Check: If the linked list is empty or contains only a single node, it is already sorted; return the head.
2. Finding the Middle: Split the list into two halves using the Tortoise and Hare (slow and fast pointer) algorithm.
3. Merging Two Sorted Lists: Combine two individually sorted sub-lists into a single sorted list (covered in earlier chapters).

Complete Merge Sort Pseudo-Code

def mergeSort(head):
    # Base Case: 0 or 1 element
    if head is None or head.next is None:
        return head
        
    # Step 1: Find the middle to split the list
    middle = findMiddle(head)
    leftHead = head
    rightHead = middle.next
    
    # Break the link to create two independent lists
    middle.next = None
    
    # Step 2: Recursively sort both halves
    leftSorted = mergeSort(leftHead)
    rightSorted = mergeSort(rightHead)
    
    # Step 3: Merge the two sorted halves
    return mergeTwoSortedLists(leftSorted, rightSorted)

6. Real-World Pitfall: The Even-Length Middle Dilemma

When finding the middle of a linked list using standard slow and fast pointers, an important edge case emerges regarding even-length lists.

The Problem

In standard cycle-detection or middle-finding algorithms, the fast pointer starts at head, and upon termination, the slow pointer lands on the second middle element for even-sized lists.

• Why does this break Merge Sort? If a list has 2 nodes (1 -> 2), landing on the second middle means leftHead gets both nodes, and rightHead gets null. This results in infinite recursion because the problem size never shrinks!

The Solution: Fast Pointer Offset

To ensure the slow pointer lands on the first middle element (so the left sub-list gets the correct partition), initialize the fast pointer one step ahead at head.next.

def findMiddle(head):
    if head is None:
        return head
        
    # Initialize fast pointer one step ahead to grab the FIRST middle in even lengths
    slow = head
    fast = head.next 
    
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        
    return slow

7. Complete Flow Walkthrough (Dry Run)

Let us trace sortList([3, 4, 2, 1, 5]):

1. Initial Call: head = 3

   • findMiddle([3, 4, 2, 1, 5]) returns node 2.
   • Split into leftHead = [3 -> 4 -> 2] and rightHead = [1 -> 5].
   • Disconnect: middle.next = None (now 2 points to null).

2. Left Branch Recursion ([3 -> 4 -> 2]):

   • Middle of [3 -> 4 -> 2] is 4. Split into [3 -> 4] and [2].
   • Sub-split [3 -> 4] into [3] and [4]. Base case reached.
   • Merge [3] and [4] $\rightarrow$ [3 -> 4].
   • Merge [3 -> 4] and [2] $\rightarrow$ [2 -> 3 -> 4].

3. Right Branch Recursion ([1 -> 5]):

   • Middle of [1 -> 5] is 1. Split into [1] and [5]. Base case reached.
   • Merge [1] and [5] $\rightarrow$ [1 -> 5].

4. Final Merge:

   • Merge sorted lists [2 -> 3 -> 4] and [1 -> 5].
   • Comparison yields: 1 $\rightarrow$ 2 $\rightarrow$ 3 $\rightarrow$ 4 $\rightarrow$ 5.
   • Returns the new sorted head (1).

8. Comparative Strategy Synthesis

9. Summary and Key Takeaways

• Problem Definition: Sorting a linked list requires rearranging node pointers (or values) to achieve non-decreasing order while returning the updated head.
• Naive Limit: Extracting elements into an array, sorting, and rewriting takes $O(N \log N)$ time but fails space constraints by consuming $O(N)$ extra space.
• Optimal Choice: Merge Sort is the preferred sorting algorithm for linked lists due to its natural alignment with sequential access and divide-and-conquer logic.
• In-Place Execution: Merge Sort on linked lists achieves an auxiliary space complexity of $O(1)$ beyond the recursion stack ($O(\log N)$), avoiding external data structures.
• The Middle Pointer Edge Case: Always adjust the Tortoise and Hare initialization (fast = head.next) to capture the first middle in even-length lists, preventing infinite recursion loops.
• Recursive Structure: The algorithm relies on three steps: finding the middle, breaking the list, recursively sorting left and right halves, and merging the two sorted lists.