# Linked List Merge Sort

- Linked List Merge Sort Algorithm
- Linked List Merge Sort Illustration
- Linked List Merge Sort Implementation
- Linked List Merge Sort Algorithm Complexity

In this tutorial, we will learn how to sort a linked list using the Merge Sort algorithm. It is one of the most preferred algorithms for sorting a linked list because slow random access of pointers makes other algorithms perform poorly( example: quicksort and heapsort).

## Linked List Merge Sort Algorithm

Let the `head`

be the first node of the linked list to sort.

`mergeSort(head)`

##### If the linked list is empty or has

`1`

node, it is already sorted. Return the linked list as it is.##### Get the

`mid`

node and its previous node`prev`

using the`getMid()`

function.##### Set

`prev->next`

to`NULL`

to break the linked list into two equal parts.##### Recursively call

`mergeSort(head)`

and`mergeSort(mid)`

to sort the two smaller linked lists.##### Merge the two sorted linked lists using the

`merge(head, mid)`

function.

`getMid(head)`

We take two pointers, one `slow`

and one `fast`

, the `fast`

pointer covers the linked list at twice the speed of `slow`

, and the `slow`

pointer lands at the `mid`

node when the `fast`

node lands at the end of the linked list. We also take a `prev`

node to handle the splitting of linked lists in the `MergeSort()`

function.

##### Initialize

`mid`

as`head`

,`fast`

as`head`

, and`prev`

as`NULL`

.##### While

`fast`

!=`NULL`

and`fast->next`

!=`NULL`

, do the following:`prev`

=`mid`

, store reference to the pointer before mid to split lists.`mid`

=`mid->next`

, move mid at a speed of`1`

node per iteration.`fast`

=`fast->next->next`

, move`fast`

at a speed`2`

times that of`mid`

.

##### return a pair of nodes containing both

`prev`

and`mid`

.

`merge(F,B)`

`F`

is the head of the first part of the linked list, and `B`

is the head of the second part of the linked list. We merge both sorted sublists, `F`

and `B`

, to get the final sorted linked list.

##### Initialize

`first`

pointing towards`F`

and`second`

pointing towards`B`

. Also, initialize`merged`

with`NULL`

to hold the merged sorted list and`tail`

to manage the end of the sorted list.##### While we do not run out of either

`first`

or`second`

, do the following:Compare

`first`

with`second`

to find the lesser element and initialize`insertedNode`

with it.`if (`first->data` < `second->data`) { `insertedNode` = `first`; `first` = `first->next`; } else { `insertedNode` = `second`; `second` = `second->next`; }`

If

`merged`

is empty, initialize it with`tail`

.Append

`insertedNode`

at the end of tail and move the tail pointer ahead.` `tail->next` = `insertedNode` `tail` = `insertedNode``

##### If there are remaining elements in

`F`

do the following:- Append
`first`

to`tail`

’s end and move tail pointer ahead,`tail->next`

=`first`

,`tail`

=`first`

. - Move
`first`

one node ahead,`first`

=`first->next`

.

- Append
##### If there are remaining elements in

`S`

do the following:- Append
`second`

to`tail`

’s end and move tail pointer ahead,`tail->next`

=`second`

,`tail`

=`second`

. - Move
`second`

one node ahead,`second`

=`second->next`

.

- Append
##### Append

`NULL`

to`tail`

’s end and return the`merged`

sorted list.

## Linked List Merge Sort Illustration

##### Let’s take the linked list

`3 -> 2 -> 4 -> 1 -> NULL`

##### We split it into two linked lists

`3 -> 2 -> NULL`

and`4 -> 1 -> Null`

##### We split

`3 -> 2 -> Null`

into`3 -> Null`

and`2 -> Null`

, Merge them to get sorted sub-list`2 -> 3 -> Null`

##### We split

`4 -> 1 -> Null`

into`4 -> Null`

and`1 -> Null`

, Merge them to get sorted sub-list`1 -> 4 -> Null`

##### Merge

`2 -> 3 -> Null`

and`1 -> 4 -> Null`

to get the sorted linked list as`1 -> 2 -> 3 -> 4 -> Null`

.

## Linked List Merge Sort Implementation

```
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int x) {
this->data = x;
this->next = NULL;
}
};
pair<Node*, Node*> getMid(Node* head) {
Node* mid = head;
Node* fast = head;
Node* prev = NULL;
while (fast != NULL && fast->next != NULL) {
prev = mid;
mid = mid->next;
fast = fast->next->next;
}
pair<Node*, Node*> result(prev, mid);
return result;
}
Node* merge(Node* F, Node* B) {
Node* first = F;
Node* second = B;
Node* merged = NULL;
Node* tail = NULL;
while ((first != NULL) && (second != NULL)) {
Node* insertedNode = NULL;
if (first->data < second->data) {
insertedNode = first;
first = first->next;
}
else {
insertedNode = second;
second = second->next;
}
if (merged) {
tail->next = insertedNode;
tail = insertedNode;
}
else {
merged = tail = insertedNode;
}
}
while (first != NULL) {
tail->next = first;
tail = first;
first = first->next;
}
while (second != NULL) {
tail->next = second;
tail = second;
second = second->next;
}
if (tail) {
tail->next = NULL;
}
return merged;
}
void mergeSort(Node*& head) {
if ((head == NULL) || (head->next == NULL)) {
return;
}
pair<Node*, Node*>a = getMid(head);
Node* prev = a.first;
Node* mid = a.second;
if (prev) {
prev->next = NULL;
}
mergeSort(head);
mergeSort(mid);
head = merge(head, mid);
}
void printList(Node* head)
{
Node*curr = head;
while (curr != NULL) {
cout << curr->data << " ";
curr = curr->next;
}
cout << "\n";
}
int main()
{
Node* head = new Node(5);
head->next = new Node(6);
head->next->next = new Node(4);
head->next->next->next = new Node(3);
head->next->next->next->next = new Node(2);
head->next->next->next->next->next = new Node(1);
printList(head);
mergeSort(head);
printList(head);
return 0;
}
```

## Linked List Merge Sort Algorithm Complexity

### Time Complexity

- Average Case

Merge sort is a recursive algorithm. The following recurrence relation gives the time complexity expression for Merge sort.

```
T(n) = 2T(n/2) + θ(n)
```

This result of this recurrence relation gives `T(n) = nLogn`

. We can also see it as a linked list of size `n`

being divided into a maximum of `Logn`

parts. Sorting each part and merging each of them takes `O(n)`

time.

Hence the time complexity is of the order of [Big Theta]: `O(nlogn)`

.

- Worst Case

The worst-case time complexity is [Big O]: `O(nlogn)`

. It is the same as average-case time complexity.

- Best Case

The best-case time complexity is [Big Omega]: `O(nlogn)`

. It is the same as the worst-case time complexity. But if the linked list is already sorted, we can reduce the time complexity to `O(n)`

.

### Space Complexity

The space Complexity for the Merge Sort algorithm on the linked list is `O(logn)`

due to the space occupied by the recursive calls in the stack. If we ignore the space taken by recursive calls, the space complexity can be considered as `O(1)`

.