## What is it? Sort a singly linked list efficiently using Merge Sort. Unlike arrays, Merge Sort is the preferred algorithm for linked lists because it does not require random access and can be done in O(1) extra space. ## How it works 1. **Find middle** — using fast/slow pointers 2. **Split** — break the list into two halves 3. **Recursively sort** each half 4. **Merge** — merge the two sorted halves using the standard merge procedure 5. Return the merged (sorted) head ## When to use - Sorting a linked list where Quick Sort is inefficient (no O(1) access to pivot position) - When stable sort is required - O(n log n) guarantee needed for linked list sorting ## Key Points - O(n log n) time, O(log n) space (recursion stack) - Stable sort — equal elements maintain relative order - Bottom-up Merge Sort achieves O(1) space but is more complex to implement