Last Updated: Mar 27, 2024
Difficulty: Medium

# The Merge Sort for Doubly Linked List

## Introduction

Merge Sort and Linked Lists are both hot topics when it comes to tech interviews, But what happens when we mix up these topics and the question that is asked to us is â€˜Merge Sort for Doubly Linked Listâ€™. Now we know that merge sort is a sorting technique that works on the principle of Divide and Conquer, and a Doubly Linked List is a linked list that contains the address of both its next and previous pointers. Let us now see how we can sort a doubly-linked list using merge sort.

Recommended Topic, Floyds Algorithm and Rabin Karp Algorithm

## Problem Statement

The problem that is given to us is fairly simple to understand, we are given an unsorted doubly linked list, and we have to sort it using merge sort.

Letâ€™s say that the linked list that is given to us is

Then after applying merge sort to this list, we will get the following as our final answer.

## Approach

In the image above, we can see the functioning of the merge sort. In merge sort, we divide the list into two smaller lists at each step and call the same function recursively on both the smaller parts. From recursion, we get two sorted lists which are then merged by a function, letâ€™s say, merge(), and the final output is a sorted list.

But how will we apply this to doubly linked lists?

The answer is simple. We will first find the middle node of the linked list. You can refer here to find the middle node of a linked list. Then we will split the linked list around the middle node and make two recursive calls on both these sub-linked lists. Finally, we will be merging the two sorted lists (returned from the recursive calls above).

How to code the merge() function?

The function will take two parameters,i.e., â€˜FIRST_LISTâ€™ and â€˜SECOND_LISTâ€™, and will check for the following cases:

1) If â€˜FIRST_LISTâ€™ is NULL, return â€˜SECOND_LISTâ€™.

2) If â€˜SECOND_LISTâ€™ is null, return â€˜FIRST_LISTâ€™.

3) If â€˜FIRST_LIST->DATAâ€™ is less than â€˜SECOND_LIST->DATAâ€™, then we will append â€˜FIRST_LISTâ€™ to the resultant list otherwise we will append â€˜SECOND_LISTâ€™.

Now letâ€™s have a look at the final code for better understanding.

### Code

``````#include <iostream>
using namespace std;

// Doubly linked list node class.
class Node
{
public:
int data;
Node *next, *prev;

// Constructor.
Node(int data)
{
this->data = data;
next = NULL;
prev = NULL;
}
};

// This function divides the linked list into two parts and returns the head of second half.
{
while (fastPointer != NULL && fastPointer->next != NULL &&
fastPointer->next->next != NULL)
{
fastPointer = fastPointer->next->next;
slowPointer = slowPointer->next;
}
Node *secondHalf = slowPointer->next;

// Separating the second part.
slowPointer->next = NULL;
return secondHalf;
}

// This function will merge two lists and will return the sorted list.
Node *merge(Node *firstList, Node *secondList)
{
// If the 'firstList' linked list is empty, then we dont have to merge.
if (firstList == NULL)
return secondList;

// If the 'secondList' linked list is empty, then donâ€™t have to merge.
if (secondList == NULL)
return firstList;

// Regular merge conditions.
if (firstList->data > secondList->data)
{
secondList->next = merge(firstList, secondList->next);
secondList->next->prev = secondList;
secondList->prev = NULL;
return secondList;
}
else
{
firstList->next = merge(firstList->next, secondList);
firstList->next->prev = firstList;
firstList->prev = NULL;
return firstList;
}
}

// It returns the sorted doubly linked list.
{
}

}

Node *firstList = NULL, *secondList = NULL;
// Splitting the list.

// Recursively calling merge sort on both the sublists.
secondList = mergeSort(secondList);

// Merging the two sorted sub lists.
Node *sortedList = merge(firstList, secondList);
return sortedList;
}

// Print function.
{
while (temp != NULL)
{
cout << temp->data << " ";
temp = temp->next;
}
}

// Main function.
int main()
{
int n;
cout << "Enter the number of elements in the list: ";
cin >> n;

cout << "Enter the elements: ";
Node *head = NULL, *tail = NULL;

for (int i = 0; i < n; i++)
{
int data;
cin >> data;
Node *newNode = new Node(data);
if (i == 0)
{
}
else
{
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
}
}
cout << "Sorted list: ";

// Calling the 'mergeSort()' function to sort the doubly linked list.

// Printing the final list.
return 0;
}``````

Input

``````Enter the number of elements in the list: 6
Enter the elements: 8 9 12 2 18 20``````

Output

``Sorted list: 2 8 9 12 18 20``

### Complexities

Time Complexity

O(N * log N), where â€˜Nâ€™ is the length of the array.

Here in the worst case split operation takes O(N), the merge operation takes O(N) time and the recursive function will be called O(log N) times so the overall complexity would be (O(N) + O(N)) * O(log(N)) ~ O(N * log(N)).

Space Complexity

O(log (N)), where â€˜Nâ€™ is the length of the doubly linked list.

As we are using a recursive function and it would take O(log (N)) space for the recursive stack.

### What is a linked list?

A linked list is a dynamic data structure in which each element (called a node) consists of two components: data and a reference (or pointer) to the next node. A linked list is a collection of nodes, each of which is linked to the next node by a pointer.

### How is the linked list implemented in memory?

LinkedList, unlike Arrays, is not stored in a contiguous memory location. Each element in the list is distributed across memory and is linked by pointers in the Node. As a result, separate memory space is allocated large enough to store both the key and the pointer to the next element whenever a new element is added.

### What is the use of a doubly linked list?

It is used in navigation systems where both forward and backward navigation is required. The browser uses a back and forward button to implement backward and forward navigation of visited web pages. It is also used to represent a traditional card game deck.

## Conclusion

We saw how we could apply merge sort on doubly linked lists and also revised concepts on finding the middle part of and merging doubly-linked lists. Now doubly linked lists is a vast topic, and this was just the beginning of your journey in becoming a star coder.

Recommended Problems -

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!

Topics covered
1.
Introduction
2.
Problem Statement
3.
Approach
3.1.
Code
3.2.
Complexities
4.