Sort List — Merge Sort
Difficulty: Hard
Asked in: Amazon, Google
Understanding The Problem
Problem Description
Sort a linked list using Merge Sort.
Example 1
Input: 44>2>14>37
Output: 2>14>37>44
Explanation: After sorting, 44>2>14>37 becomes 2>14>37>44.
Solution
Read about linked list properties from here.
The most preferable sorting technique used for sorting a linked list is Merge Sort. All other sorting algorithms are quadratic algorithms and approaches like Quick Sort and Heap sort perform poorly due to the fact that of slow random access of the linked list.
Let's take 3 > 2 > 4 > 1 > Null for example
We separate 3 > 2 > 4 > 1 > Null into 3 > 2 > Null and 4 > 1 > Null;
We separate 3 > 2 > Null into 3 > Null and 2 > Null;
Merge them into 2 > 3 > Null;
We separate 4 > 1 > Null into 4 > Null and 1 > Null;
Merge them into 1 > 4 > Null;
Merge 2 > 3 > Null and 1 > 4 > Null into 1 > 2 > 3 > 4 > Null.
You must have read about Merge sort in an array that uses the divide and conquer approach. We will do the sorting for the linked list in a similar way as we did in sorting the array.
Definition of the singly linked list passed to the function:
class ListNode {
int val;
ListNode *next;
};
So, we will have to understand how subproblems will look like. Imagine a sublinked list with a
head
pointer. Here’s how merge sort uses divideandconquer:
 Divide — We will divide the list into two sublists and will try to sort them.
 Conquer — We recursively sort the two sublists of approximately n /2, nodes in each, takes some amount of time, but we’ll account for that time when we consider the subproblems.
 Combine — The two sublists returned will be sorted, we will try to merge them in O(n).
In conclusion, there will be 3 different functions required.
 mergeSort(): A recursive function that will take Linked list’s head pointer in the argument. It will first divide the list into two different halves, and then will merge them.
 findHalves() : This function will divide a linked list into two halves. For this purpose, we can use the concept of slow and fast pointers. Read here .
 merge() : This function will take two linked list and return a single sorted linked list. The idea is to compare the current node of both the lists and add a node with smaller value to the output list. After this, let the recursion handle the merging of the remaining list. Read here.
The solution will be recursive, so we will need a base case for the mergeSort function. The base case will be the case when the linked list has none or only one element, in that way the list with zero or one node is already sorted.
Try solving this problem here .
Pseudo Code
ListNode sortList(ListNode head) {
if(head is NULL or head.next is NULL)
return head
return mergeSort(head)
}
ListNode mergeSort(ListNode head)
{
if(head is NULL or head.next is NULL)
return head
ListNode list1
ListNode list2
// Divide linked list into two halves
// list1 and list2 are passed by reference
findHalves(head, &list1, &list2)
ListNode a = mergeSort(list1)
ListNode b = mergeSort(list2)
// merge the two lists
return merge(a,b)
}
ListNode merge(ListNode List1, ListNode List2)
{
ListNode result = NULL
if(List1 == NULL)
return list2
if(List2 == NULL)
return list1
if(List1.val <= List2.val)
{
result = List1;
result.next = merge(List1.next, List2)
}
else
{
result = List2;
result.next = merge(List1, List2.next)
}
return result
}
void findHalves(ListNode head, ListNode list1, ListNode s2) {
ListNode slow = head
ListNode fast = head
while(fast != NULL)
{
fast = fast.next
if(fast != NULL and fast.next != NULL)
{
slow = slow.next
fast = fast.next
}
}
s1 = head
s2 = slow.next
slow.next = NULL
}
Complexity Analysis
Time Complexity: O(n log n)
Space Complexity: O(n log n)
Critical Ideas To Think
 How the merge function merged two unsorted linked lists into one? Answer : The merge function is actually not merging two unsorted linked list. When we divided the linked list until the list has only one node, then that represented a sorted linked list with only one node and the merge function merges such two linked lists with one node and returns the bigger sorted linked list with two nodes. Then it again receives such two sorted lists with two nodes and merges them in a sorted manner forming a linked list of 4 nodes, and in this way, it goes on and ultimately sort the whole linked list.

How is the space complexity O(n log n)?
Answer:
The divide operation uses log(n) recursion stacks to divide the lists and on each stack, we have a merge function using n recursion stacks to merge two linked lists of
n
nodes. 
Why did we pass list1 and list2 as a reference in
findHalves()
?  What changes should we perform in the above approach to sort the list in descending order?
 Is this approach similar to merge sort in an array? How?
Critical Concepts to explore in Linked List
 Types of Linked List
 Basic Operation on Linked List
 Merge two sorted lists
 Find the middle of the linked list
 Merge k sorted lists
Suggested Problems to solve in Linked List
 Merge sort in an array
 Reverse linked list
 Middle of the Linked List
 Remove Duplicates from Sorted List
 Merge Sort on Linked List
 Check if a singly linked list is palindrome
 Detect and Remove Loop in a Linked List
 Sort a linked list using insertion sort
 Remove Nth Node from List End
 Odd even linked List
Happy coding! Enjoy Algorithms.