Harshit Jindal Oct 12, 2023

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.

### `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.

• ##### 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`.

### `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.

• ##### 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.
```c++
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`.
• ##### 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`.

## 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;
}
};

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;
}

return;
}
Node* prev = a.first;
Node* mid = a.second;

if (prev) {
prev->next = NULL;
}

mergeSort(mid);
}

while (curr != NULL) {
cout << curr->data << " ";
curr = curr->next;
}
cout << "\n";
}

int main() {
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)`.

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.