Merge Sort for Linked Lists

Problem Statement

Given a singly linked list, use the merge sort algorithm to sort the list in the ascending order of their node's values.

Example

Input

Output

Example Explanation

The nodes in the input are not arranged in any particular order, while they are arranged in ascending order of their value in the output.

Constraints

• $0 < n < 10^5,$ where $n$ is the number of nodes.
• $-10^9 < \text{node.val} < 10^9$

Algorithm 1

Merge sort for linked lists is preferred to sort linked lists because accessing a random node in a linked list is a costly operation which makes other algorithms like quicksort, heapsort, etc inefficient.

The algorithm of merge sort for linked lists is quite similar to sorting an array using merge sort. We will be having a recursive function mergeSort which divides the list into two halves and recurse back for the left and the right half. After that, we will have another function mergeSorted which will be used to merge the sorted parts.

The steps required in the algorithm are as follows - mergeSort(head) -

• Let the function be mergeSort that accepts a single argument head which denotes the pointer to the head of the linked list.
• In the function, firstly we will check if the head itself is null or if the list with its head node as head consists of only one node. If any of the above conditions is found to be true, we will simply return head.
• Now we will find the middle node of the liked list whose head node is head, let it be mid.
• Now we will divide the list into two halves, therefore we will remove the next link of the mid node $i.e.$ mid.next = null.
• Recur for the left and right half of the partitioned list, let the node returned by them be left and right respectively.
• Call the mergeSorted function to merge the sorted left part and the sorted right part. Let after merging two individually sorted parts, the head node of the combined linked list is answer.
• Return the answer node which represents the head of the sorted linked list.

The steps required to merge the sorted parts are as follows - mergeSorted(left, right) -

• Let the function mergeSorted accepts two arguments of node type left and right denoting the head of two independent sorted lists.
• Now we will have some base conditions -
  • If left is null then return right.
  • Else if right is null then return left.
• Then we will declare a node type variable res to store the result.
• Now we will check if left.val is smaller than or equal to right.val, then we will assign left to res and recurse for the left.next and assign the obtained result to res.next.
• Now we will check if left.val is greater than right.val, then we will assign right to res and recurse for the right.next and assign the obtained result to res.next.
• At last we will return the res as our answer.

Java Implementation

Output -

C++ Implementation

Output -

Python Implementation

Output -

Complexity Analysis

• Time Complexity - At each iteration, we are dividing the list into two halves and in each step, we are merging the divided parts. Since the merging step requires $O(n)$ time and there are $O(\log_2{n}$] iterations, therefore, the overall time complexity is $O(n\log_2{n})$.
• Space Complexity - Since both of the used functions (mergeSort and mergeSorted) are recursive in nature they will require $O(\log_2{n})$ and $O(n)$ recursive stack space respectively. Hence, the overall space complexity is $O(n)$.

Approach 2

In our last algorithm, we have seen how to use merge sort for linked lists. In this approach, we will be seeing the same concept again and will try to reduce the space complexity of the algorithm. Last time we implemented mergeSorted() function in a recursive manner which is why it required $O(n)$ recursive stack space. But this time we will try to optimize it such that mergeSorted() function will require constant extra space.

The algorithm of the mergeSort() function is the same as in the previous section, hence we are not including it again. However, the mergeSorted() algorithm is now changed and is as follows - mergeSorted(left, right)

• Let the arguments accepted by the mergeSorted() function be nothing but the heads of already sorted linked lists.
• As part of our base condition we will be checking if any of the lists is empty.
• Then we will declare a node type variable dummy with value 1 and another node type variable node that will point to dummy. The dummy will help to return the answer at the end of the function and the node is required to traverse the list.
• Now we will use a while loop to traverse until either of the left or rightpointer does not point to null and do the following -
  • If left's val is smaller than or equal to right's val then -
    • Assign left to node.next.
    • Move left to its next pointer.
  • Otherwise, left's val is greater than right's val -
    • Assign right to node.next.
    • Move right to its next pointer.
  • At last move node to its next pointer $i.e.$ node = node.next.
• After exiting from loop we will be including the nodes left out in the lists. Therefore, we will iterate until the left pointer does not start pointing to null and do the following -
  • Assign left to node.next.
  • Move left to its next pointer.
  • Move node to its next pointer $i.e.$ node = node.next.
• We will repeat the above process for the right list $i.e.$ iterate until the right pointer does not start pointing to null and do the following -
  • Assign right to node.next.
  • Move right to its next pointer.
  • Move node to its next pointer $i.e.$ node = node.next
• Now the merging part is done, we just need to return the head of the merged list which is pointed by dummy.next. Therefore, we will simply return dummy.next.

Java Implementation

Output -

C++ Implementation

Output -

Python Implementation

Output -

Complexity Analysis

• Time Complexity - Again, at each iteration we are dividing the list into two halves and in each step, we are merging the divided parts. Since the merging step requires $O(n)$ time and there are $O(\log_2{n})$ iterations, therefore, the overall time complexity is $O(n\log_2{n})$.
• Space Complexity - Since the mergeSort function is a recursive function that requires $O(\log_2{n})$ recursive stack space, therefore the overall space complexity is $O(\log_2{n})$.