Sort List - Merge Sort

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 sub-linked list with a head pointer. Here’s how merge sort uses divide-and-conquer:

Divide — We will divide the list into two sub-lists 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 sub-lists 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?