Merge Sort for Linked Lists

Problem Statement

Given the head of a linked list, sort it in ascending order using merge sort algorithm. Merge sort is particularly well-suited for linked lists because it doesn't require random access to elements.

Example

Input: 4 -> 2 -> 1 -> 3 -> null Output: 1 -> 2 -> 3 -> 4 -> null Input: -1 -> 5 -> 3 -> 4 -> 0 -> null Output: -1 -> 0 -> 3 -> 4 -> 5 -> null Input: null Output: null

---

Brute Force Approach (Bubble Sort / Selection Sort)

Intuition

We can use simple sorting algorithms like bubble sort on linked lists by repeatedly swapping values. However, this is O(n²) which is inefficient.

Algorithm (Bubble Sort)

1. Repeat n times:
2. Traverse the list
3. If current value > next value, swap values
4. Continue until no swaps needed

Implementation

Complexity Analysis

• Time Complexity: O(n²) - Nested iterations
• Space Complexity: O(1) - Only swapping values

---

Optimal Approach (Merge Sort)

Intuition

Merge sort is ideal for linked lists because:

1. Finding the middle element is O(n) using slow-fast pointers
2. Merging two sorted lists is O(n) and doesn't require extra space
3. Overall complexity is O(n log n)

The algorithm:

1. Find the middle of the list
2. Recursively sort both halves
3. Merge the two sorted halves

Algorithm

1. Base case: If list has 0 or 1 nodes, return
2. Find the middle using slow-fast pointer technique
3. Split the list into two halves
4. Recursively sort both halves
5. Merge the sorted halves

Visualization

Input: 4 -> 2 -> 1 -> 3 Split: 4 -> 2 1 -> 3 | | Split again Split again 4 2 1 3 | | | | Merge Merge 2 -> 4 1 -> 3 | | └───────┬───────┘ | Final Merge 1 -> 2 -> 3 -> 4

Implementation

Complexity Analysis

• Time Complexity: O(n log n) - Divide and conquer
• Space Complexity: O(log n) - Recursive call stack

---

Bottom-Up Merge Sort (Iterative - O(1) Space)

Intuition

Instead of top-down recursion, we can use bottom-up approach:

1. Start with sublists of size 1
2. Merge adjacent sublists
3. Double the size and repeat

This avoids recursive call stack.

Implementation

Complexity Analysis

• Time Complexity: O(n log n) - Same as recursive
• Space Complexity: O(1) - No recursion

---

Comparison with Array Merge Sort

| Aspect | Array | Linked List | |--------|-------|-------------| | Random Access | O(1) | O(n) | | Finding Middle | O(1) | O(n) | | Merge Extra Space | O(n) | O(1) | | Overall Space | O(n) | O(log n) or O(1) |

---

Key Takeaways

1. Merge sort is ideal for linked lists due to efficient merging
2. Finding middle uses the slow-fast pointer technique
3. Start fast at head.next for correct splitting
4. The merge step is the core operation - reusing nodes, no extra space
5. Bottom-up approach achieves O(1) space by avoiding recursion
6. This is a very important interview problem testing multiple concepts
7. Time complexity is O(n log n) which is optimal for comparison-based sorting