The linked list is a very popular data structure that has many applications in the real world. If you’re preparing for an interview, as a software engineer or developer, there’s a good chance that you might face a problem that requires sorting a linked list. Merge sort is one of the few algorithms which can do this efficiently. 

So, if you’re preparing for technical interviews, this article is very important for you! We will be covering the following:

• What Is Merge Sort?
• How Does Merge Sort Work on a Linked List?
• Tortoise and Hare Approach
• Algorithm and Explanation
• Pseudocode
• Code
• Output
• Time and Space Complexity
• FAQs

Applying merge sort on a linked list is a little bit trickier than using merge sort on an array. So, we highly recommend you to read this article on merge sort before reading this one.

What Is Merge Sort?

Merge sort is an efficient way of sorting a list of elements. It is a comparison-based sorting algorithm. It belongs to the divide-and-conquer paradigm, wherein we divide the problem into subproblems, solve them individually, and combine their solutions to form the solution to the original problem.

How Does Merge Sort Work on a Linked List?

It works on a linked list in the same way it works on an array. It recursively divides the list into two parts until we have sublists of size one. Then we combine them in a manner so that they give a sorted list.

Merge sort works on an array in the following manner:

In this article, for a linked list containing N nodes, we will use the term “middle position” to denote the ceil(N/2)th position (considering 1-based indexing). Here are a couple of examples:

• Odd number of elements: If the number of elements is five, we will consider the ceil(5/2)th element (the third element) to be the middle element
• Even number of elements: If the list has four elements, we will consider ceil(4/2)th element (the second element) to be the middle element.

As we can see, in a list of size N, we split the list at the middle position. 

Unlike an array, the linked list does not support random access. It only supports sequential access. This means, in an array, we can access any element in O(1). However, to access any element in a linked list, we need to linearly iterate over the entire linked list. Therefore, the time required is O(i) to access the ith element of the linked list.

A linked list data structure is used mainly when the size of the data is unknown or dynamic. We only know the head pointer and the fact that the last element in the linked list will be pointing to NULL. These limitations make it difficult to find the middle point of the linked list. However, there exists a method known as the “Tortoise and Hare Approach” to do this.

Tortoise and Hare Approach

In this method, we take two pointers:

• Slow: Pointing to the first element of the list
• Fast: Pointing to the second element of the list

If there’s only one element in the list, the second pointer will point to the null pointer. 

At each step, we move the slow pointer by one step and the fast pointer by two steps. In doing so, when the fast pointer either reaches the last element of the linked list or it points to a null pointer, the slow pointer would have reached the middle of the list.

More precisely, in an odd-length linked list, the fast pointer reaches the null pointer whereas, in an even-length linked list, the fast pointer reaches the last element at the same iteration when the slow pointer reaches the middle element.

See the following figures to visualize it. Initially, the slow pointer is at the beginning, and the fast pointer is at the second element.

The slow pointer moves by 1 and reaches 2; the fast pointer moves by 2 and reaches 4.

Again, the slow pointer moves by 1 and reaches 3; the fast pointer moves by 2 and reaches the null pointer.

As you can see, when the fast pointer reaches the null pointer, the slow pointer reaches the middle of the linked list. If we have a linked list containing an even number of elements, the slow pointer will be at the middle element when the fast pointer is at the last element.

Algorithm for Sorting a Linked List Using Merge Sort

The algorithm is the same as merge sorting an array.

Step 1: Dividing the Lists Into Two Smaller Sublists

We will keep on recursively dividing the lists into two smaller sublists until the size of each sublist becomes 1. We will calculate the middle point of the linked list using the tortoise and hare approach, as explained above.

Have a look at the following figure to see how a linked list gets broken down.

Step 2: Merging the Sublists to Produce a Sorted List

In this step, we merge the linked list similarly as we used to merge them in an array. 

Let’s assume the two sorted lists are A: [1, 4, 5, 6] and B: [2, 3, 8, 7], and we are storing the merged and sorted linked list in C. The image below shows a few steps on how we merge two sorted linked lists. The rest of the steps are the same as that of merging two sorted arrays.

The linked list comes with a disadvantage: that it couldn't be randomly accessed. On the other hand, it gives us the flexibility to remove the head from a linked list in O(1) complexity. Also, adding an element at the end of the linked list is also O(1). 

So, while merging, we don’t need an auxiliary array to store the elements in the correct order; instead, we can remove the head node from a list, append it to the end of the sorted list and move the pointer to the next node using “next” pointer (if possible). Therefore, by exploiting the “next” pointer concept, we can achieve O(1) auxiliary memory in merging two sorted lists.

Pseudocode for Sorting a Linked List Using Merge Sort

Here is the pseudocode for the above algorithm. Understand it thoroughly and implement it in any language of your choice.

Function: tortoiseAndHareApproach (Node start)
  pointer slow = start
  pointer fast = next of start
  while(fast is not null and next of fast is not null)
      slow = next of slow
      fast = next of next of fast
  return slow


Function: merge (list A, list B)
  list C
  pointer ptr_A = beginning of A
  pointer ptr_B = beginning of B
  pointer ptr_C = beginning of C
  while(ptr_A is not equal to end of A and ptr_B is not equal to end of B)
      if( element at ptr_A is less than element art ptr_B)
        append element at ptr_A to C
        move ptr A to next element in A
      else ( element at ptr_B is less than element art ptr_A)
        append element at ptr_B to C
        move ptr B to next element in B
    if ( ptr_A is equal to end of A)
      // there may be some elements left in B
      while (ptr_B is not equal to end of B)
          append element at ptr_B to C
          move ptr B to next element in B
    else
        while (ptr_A is not equal to end of A)
        append element at ptr_A to C
        move ptr A to next element in A


Function: mergeSort (node st)
  if (next of st == null)
      return st
  pointer ptr_mid = tortoiseAndHareApproach (st)
  pointer start_of_right = next of ptr_mid
  next of ptr_mid = null
  list left_sorted = mergeSort (st)
  list right_sorted = mergeSort (start_of_right)
  pointer sorted_st = mergeSort (left_sorted, right_sorted)
  return sorted_st

Code for Sorting a Linked List Using Merge Sort

We hope you have tried implementing the pseudocode. Here is the implementation for the above algorithm in C++ to sort the array in increasing order. 

#include <iostream>
using namespace std;

struct node
{
    int data;
    node *next;
    node()
    {
        data = 0;
        next = NULL;
    }
};

// Function to print the linked list starting from head pointer
void print(node *head)
{
    while (head != NULL)
    {
        cout << head->data << " ";
        head = head->next;
    }
    cout << '\n';
}

// Function to calculate the mid point of linked list
node * tortoiseAndHareApproach(node *head)
{
    node* slow = head;
    node* fast = head->next;
    while (fast != NULL && fast->next != NULL)
    {
        slow = slow->next;
        fast = (fast->next)->next;
    }
    // slow must be pointing at the middle element of the list
    return slow;
}

// Function to take two sorted linked lists and merge them
// to form a sorted resultant linked list
node * merge(node *left, node *right)
{

    // creating an auxiliary head node storing the 

    // the head of the linked list to be returned and 

    // another pointer to remember where the last 

    // added node was
    node *dummyHead = new node();
    node *current = dummyHead;
    
    while (left != NULL && right != NULL)
    {
        if (left->data <= right->data)
        {
            current-> next = left;
            left = left->next;
            current = current-> next;
        }
        else if (right->data < left->data)
        {
            current->next = right;
            right = right->next;
            current = current->next;
        }
    }
    while (left != NULL)
    {
        current->next = left;
        left = left->next;
        current = current->next;
    }
    while (right != NULL)
    {
        current->next = right;
        right = right->next;
        current = current->next;
    }
    return dummyHead->next;
}

// Function to recursively  divide the linked list
node * mergeSort(node *start)
{
    if (start -> next == NULL)
    {
        // only 1 element in current list
        // so return it as it is
        return start;
    }
    // finding middle of the list using
    // the tortoise and hare approach
    node *mid = tortoiseAndHareApproach(start);
    node *start_of_right = mid->next;

    // breaking the linked list into two parts
    mid->next = NULL;

    node *left = mergeSort(start);
    node *right = mergeSort(start_of_right);

    node *new_head = merge(left, right);

    return new_head;
}


// Function to push a node at the front of linked list
void push(int val, node **ptr_to_head)
{
    // create a new node
    node *temp = new node();
    // assigning value to be inserted to the new node
    temp->data = val;
    // making the link between new node and the head of the linked list
    temp->next = *ptr_to_head;
    // making new node the head of the linked list
    *ptr_to_head = temp;
}

// Driver Code
int main()
{
    node* head = NULL;
    push(7, &head);

    push(8, &head);

    push(2, &head);

    push(3, &head);

    push(6, &head);
    push(1, &head);
    push(4, &head);
    push(5, &head);
    cout << "Linked list before sorting:" << '\n';
    print(head);
    head = mergeSort(head);
    cout << "Linked list after sorting:" << '\n';
    print(head);
}

Output:

Linked list before sorting:

5 4 1 6 3 2 8 7 

Linked list after sorting:

1 2 3 4 5 6 7 8 

Time and Space Complexity

Time Complexity

The time complexity of the merge sort algorithm is O( N * log2N ) , where N is the size of the linked list. We shall prove this in three parts:

Depth of the Recursion Tree

First, let’s see the depth of the recursion tree. At each step, we are dividing the linked list into equal halves (almost equal when an odd length array is present, i.e., the middle element will go in either the left or right list). We keep on dividing the list by 2 until it becomes 1. So the depth of the recursion tree will be approximately O(log2N). Have a look at the below equations to understand the math.

Merging Two Lists

Now, let’s look at the time complexity for merging two sorted lists of sizes N and M.

We will compare the first elements of the two lists and choose whichever is the minimum, delete the link between the chosen element and its next element (if it exists), thereby removing it from that list, and put the chosen element in the sorted list. We do this until both the lists get emptied. In this manner, the merging of the lists gets completed with linear time complexity O(N+M).

Merging the Lists at a Particular Depth

In the very first step, we divide our list into two equal halves. Appending these two lists will give us back the original size. If we divide the two lists further into four lists and merge those four lists, we will again get back our original list. So, we can say that at any level, the sum over the size of lists will be equal to n.

Thus, the time complexity turns out to be O(N) for each level (where N is the size of our original list).

Total Time Complexity

Combining the above results and observations, we can see that:

Space Complexity

Since the height of the recursion tree is O(log2N), and we are creating a dummy head node at each level to store the sorted list which gets stored in the system stack, the space complexity also becomes O(log2N).

When we apply merge sort over an array, we require O(N) space but here, we only need O(log2N). We don’t need to create any auxiliary list for storing the sorted list while merging two sorted lists.

FAQs on Sorting a Linked List Using Merge Sort

Question 1: Why is merge sort preferred for sorting linked lists?

Answer: Linked list does not support random access. It only supports sequential access because the data is not stored in contiguous locations in the memory. So, if we have to find a node, we will have to traverse the entire list until the node is found. Because of this, some efficient sorting algorithms like quicksort/heapsort perform poorly.

Question 2: Does the merge sort produce a stable sort on linked lists?

Answer: Yes, the algorithm proposed above will produce a stable sort. When we merge two lists, the left and right lists, on finding equal keys, we first take the front-most element from the left list and append it to the sorted list before taking the front-most element of the right list. This way, we can preserve the relative order of equal keys.

Are You Ready to Nail Your Next Coding Interview?

Sorting algorithms interview questions feature in almost every coding interview for software developers. If you’re looking for guidance and help to nail these questions and more, sign up for our free webinar. 

As pioneers in the field of technical interview prep, we have trained thousands of software engineers to crack the toughest coding interviews and land jobs at their dream companies, such as Google, Facebook, Apple, Netflix, Amazon, and more!

Sign up now!

————

Article contributed by Divyansh Gupta