249. Merge Sort on a Linked List

A singly linked list contains n integer values in no particular order. Sort it using the merge sort algorithm (repeatedly split the list in half, sort each half, then merge the two sorted halves) and print the sorted values.

Input: The first line contains an integer n, the number of nodes. The second line contains n space-separated integers, the linked list's values in order. Output: Print the sorted values, space-separated, on one line.

1 <= n <= 10^5

Unlike merge sort on an array (which typically needs O(n) extra space for the merge step), merging linked lists needs NO extra array at all - existing nodes are simply relinked, making linked-list merge sort even more space-efficient than its array counterpart.

Sort a linked list using the merge sort algorithm: repeatedly split it in half, sort each half, then merge the sorted halves back together. Brute force: Copy all values into an array, sort the array with any standard algorithm, and rebuild the list from the sorted array - this works but doesn't exploit the fact that splitting and merging a LINKED list needs no random access or extra array at all. Optimised: Merge sort is PARTICULARLY well-suited to linked lists specifically because both its core operations - splitting in half and merging two sorted sequences - only ever require RELINKING pointers, never random-access indexing or shifting elements, unlike quicksort which relies on efficient swaps by index (something linked lists don't support well).

Walk the linked list once to copy all n values into an array, sort that array using a simple quadratic algorithm such as insertion sort, then walk the list again writing the sorted values back into the existing nodes (or rebuilding new ones) in order. This is easy to get right, but insertion sort's pairwise-shifting behaviour makes it quadratic, which is far slower than the merge sort the problem actually calls for. Time: O(n^2) Space: O(n)

Copy all values into an array as before, but sort the array with an efficient O(n log n) algorithm (array-based merge sort or a built-in sort), then write the sorted values back into the linked list. This fixes the time complexity problem of the brute approach, but it still needs a full auxiliary array the size of the list, rather than sorting the list structure itself as intended. Time: O(n log n) Space: O(n)

Recursively sort the list itself: use the slow/fast pointer technique to find the middle node and split the list into two halves without any auxiliary array, recursively merge-sort each half, then merge the two now-sorted linked lists by relinking their existing node pointers (never allocating new nodes or arrays). This matches the O(n log n) time of the array-based version but drops the O(n) auxiliary array entirely, using only O(log n) space for the recursion - the true 'sort a linked list using merge sort' solution the problem is asking for. Time: O(n log n) Space: O(log n)

1. Find the middle of the list (using slow/fast pointers) to split it into two roughly equal halves. 2. Recursively sort each half the same way (splitting further until reaching single-node base cases). 3. Merge the two now-sorted halves together using the standard two-sorted-lists merge technique.

Time: O(n log n) - the same complexity as merge sort on an array, achieved here through recursive splitting and merging via pointer relinking. Space: O(log n) for the recursion stack (versus O(n) extra space merge sort typically needs on an array, since linked-list merging doesn't need a separate output array).

n = 1 (a single node, trivially sorted) and n = 10^5 to confirm the merge sort runs in O(n log n); the input isn't stated distinct, so repeated values are possible too.

Be ready to explain explicitly WHY merge sort is generally preferred over quicksort for linked lists - quicksort's usual advantage (fast in-place swaps by array index) simply doesn't exist for linked lists, while merge sort's core operations translate naturally.