How to sort a linked list using merge sort

Merge sort is one of the most famous divide-and-conquer sorting algorithms. This algorithm can be used to sort values in any traversable data structure (i.e., a linked list).

Algorithm for merge sort

  1. If: The list contains one or fewer elements, return the same list.
  2. Else: Divide the list into halves using the splitting function.
  3. Sort: Sort ​the two halves of the list.
  4. At the end, merge the sorted lists.

The illustration below shows this algorithm:

1 of 6

Implementation

In the code below, we have used two helper functions: the SplitList() function is used to divide the list into two halves, ​and the MergeSortedList() function merges the two sorted lists, recursively.

// C++ code for linked list merged sort
#include <bits/stdc++.h>
using namespace std;
// Link list node
class node {
public:
int data;
node* next;
};
// Merging two sorted lists.
node* MergeSortedList(node* lst1, node* lst2)
{
node* result = NULL;
// Base Cases
if (lst1 == NULL)
return (lst2);
else if (lst2 == NULL)
return (lst1);
// recursively merging two lists
if (lst1->data <= lst2->data) {
result = lst1;
result->next = MergeSortedList(lst1->next, lst2);
}
else {
result = lst2;
result->next = MergeSortedList(lst1, lst2->next);
}
return result;
}
// Splitting two into halves.
// If the size of the list is odd, then extra element goes in the first list.
void SplitList(node* source, node** front, node** back)
{
node* ptr1;
node* ptr2;
ptr2 = source;
ptr1 = source->next;
// ptr1 is incrmented twice and ptr2 is icremented once.
while (ptr1 != NULL) {
ptr1 = ptr1->next;
if (ptr1 != NULL) {
ptr2 = ptr2->next;
ptr1 = ptr1->next;
}
}
// ptr2 is at the midpoint.
*front = source;
*back = ptr2->next;
ptr2->next = NULL;
}
// Merge Sort
void MergeSort(node** thead)
{
node* head = *thead;
node* ptr1;
node* ptr2;
// Base Case
if ((head == NULL) || (head->next == NULL)) {
return;
}
// Splitting list
SplitList(head, &ptr1, &ptr2);
// Recursively sorting two lists.
MergeSort(&ptr1);
MergeSort(&ptr2);
// Sorted List.
*thead = MergeSortedList(ptr1, ptr2);
}
// Printing List.
void printList(node* tnode)
{
while (tnode != NULL) {
cout << tnode->data << " ";
tnode = tnode->next;
}
}
// Push function for inserting nodes in the list.
void push(node** thead, int new_data)
{
node* new_node = new node();
new_node->data = new_data;
new_node->next = (*thead);
(*thead) = new_node;
}
// Driver Program.
int main()
{
// Empty list
node* res = NULL;
node* MyList = NULL;
// List: 10->4->15->1->2->12->54
push(&MyList, 54);
push(&MyList, 12);
push(&MyList, 2);
push(&MyList, 1);
push(&MyList, 15);
push(&MyList, 4);
push(&MyList, 10);
cout << "Unsorted Linked List: ";
printList(MyList);
cout << "\n";
MergeSort(&MyList);
cout << "Sorted Linked List: ";
printList(MyList);
return 0;
}

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved