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 nodeprev
using thegetMid()
function. 
Set
prev>next
toNULL
to break the linked list into two equal parts. 
Recursively call
mergeSort(head)
andmergeSort(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
ashead
,fast
ashead
, andprev
asNULL
. 
While
fast
!=NULL
andfast>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 of1
node per iteration.fast
=fast>next>next
, movefast
at a speed2
times that ofmid
.

return a pair of nodes containing both
prev
andmid
.
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 towardsF
andsecond
pointing towardsB
. Also, initializemerged
withNULL
to hold the merged sorted list andtail
to manage the end of the sorted list. 
While we do not run out of either
first
orsecond
, do the following:
Compare
first
withsecond
to find the lesser element and initializeinsertedNode
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 withtail
. 
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
totail
’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
totail
’s end and move tail pointer ahead,tail>next
=second
,tail
=second
.  Move
second
one node ahead,second
=second>next
.
 Append

Append
NULL
totail
’s end and return themerged
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
and4 > 1 > Null

We split
3 > 2 > Null
into3 > Null
and2 > Null
, Merge them to get sorted sublist2 > 3 > Null

We split
4 > 1 > Null
into4 > Null
and1 > Null
, Merge them to get sorted sublist1 > 4 > Null

Merge
2 > 3 > Null
and1 > 4 > Null
to get the sorted linked list as1 > 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 worstcase time complexity is [Big O]: O(nlogn)
. It is the same as averagecase time complexity.
 Best Case
The bestcase time complexity is [Big Omega]: O(nlogn)
. It is the same as the worstcase 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.
LinkedInRelated Article  Data Structure
 Circular Doubly Linked List
 Circular Linked List
 Doubly Linked List
 Linked List Deletion
 Linked List Insertion