Merge sort for single linked lists

Merge sort for single linked list in C++: In this tutorial, we will learn how to implement merge sort for single linked lists using a C++ program? By Radib Kar Last updated : August 01, 2023

Problem Statement

Write a C++ program to sort two single linked lists using merge sort technique.

Solution

Merge sort is an efficient technique for sorting linked lists using recursion. The following are the steps/algorithm for merge sort:

Split the list into two halves.
Call recursive function mergeSort() two sort the individual lists.
Merge two sorted list.

1. Split the list into two halves

We use Floyd's tortoise & hare algorithm for partitioning the linked list into two halves. We declare a slow pointer and a fast pointer. Slow pointer moves one step ahead where the fast pointer moves two step at a time. Thus when the fast pointer reaches the end of the list, the slow pointer is at the midway.

    slow=head; //head of the list
    fast=head->next;

    while(fast!=NULL){
        fast=fast->next;
        if(fast!=NULL){
            slow=slow->next;
            fast=fast->next;
        }
    }
    //split1 && split2 points to the head of the split list
    *split1=head;
    *split2=slow->next;
    //split the list by partitioning
    slow->next=NULL; //partitioning

2. Call recursive function mergeSort() two sort the individual lists

Let split1 & split2 points to the two individual list after partitioning.

We call mergeSort() recursively two sort this two list.

    mergeSort(&split1);
    mergeSort(&split2);

3. Merge two sorted list

Finally merge two sorted list into another sorted list.

We can do it by comparing elements of two list.

C++ implementation for merge sort for single linked lists

#include <bits/stdc++.h>
using namespace std;

class node {
public:
    int data; // data field
    struct node* next;
};

void display(class node* head)
{
    node* current = head; // current node set to head
    while (current != NULL) { //traverse until current node isn't NULL
        printf("%d ", current->data);
        current = current->next; // go to next node
    }
}

node* creatnode(int d)
{
    node* temp = (node*)malloc(sizeof(node));
    temp->data = d;
    temp->next = NULL;
    return temp;
}

node* mergeList(node* split1, node* split2)
{
    //merging two sorted list
    node* newhead = NULL;
    //base cases
    if (split1 == NULL)
        return split2;
    if (split2 == NULL)
        return split1;
    //recursively merge
    if (split1->data <= split2->data) {
        newhead = split1;
        newhead->next = mergeList(split1->next, split2);
    }
    else {
        newhead = split2;
        newhead->next = mergeList(split1, split2->next);
    }

    return newhead;
}

void splitList(node* head, node** split1, node** split2)
{
    //similar to flyod's tortoise algorithm
    node* slow = head;
    node* fast = head->next;

    while (fast != NULL) {
        fast = fast->next;
        if (fast != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
    }

    *split1 = head;
    *split2 = slow->next;
    //spliting
    slow->next = NULL;
}

void mergeSort(node** refToHead)
{
    node* head = *refToHead;
    node *split1, *split2;
    //base case
    if (head == NULL || head->next == NULL) {
        return;
    }
    
    //split the list in two halves
    splitList(head, &split1, &split2);
    
    //recursively sort the two halves
    mergeSort(&split1);
    mergeSort(&split2);
    //merge two sorted list
    *refToHead = mergeList(split1, split2);

    return;
}

int main()
{
    printf("creating the linked list by inserting new nodes at the end\n");
    printf("enter 0 to stop building the list, else enter any integer\n");
    
    int k, count = 1, x;
    node *curr, *temp;
    scanf("%d", &k);
    node* head = creatnode(k); //buliding list, first node
    scanf("%d", &k);
    temp = head;

    ///////////////////inserting at the end//////////////////////
    while (k) {
        curr = creatnode(k);
        temp->next = curr; //appending each node
        temp = temp->next;
        scanf("%d", &k);
    }
    cout << "before merge sort...\n";
    display(head); // displaying the list
    cout << "\nafter merge sort...\n";
    mergeSort(&head);
    display(head);
    
    return 0;
}

Output

creating the linked list by inserting new nodes at the end
enter 0 to stop building the list, else enter any integer
6 5 4 7 1 0
before merge sort...
6 5 4 7 1
after merge sort...
1 4 5 6 7

Example with explanation

Let the linked be
6->5->4->7->1->NULL
Head=6
----------------------------------------------------------------

mergeSort(6)
6 !=NULL
6->next !=NULL
Call to splitList(6,split1,split2)
----------------------------------------------------------------

In splitList(6,split1,split2):
slow=6
fast=6->next=5
iteration 0:
5!=NULL
fast=5->next=4
4!=NULL
slow=6->next=5
fast=4->next=7
iteration 1:
7!=NULL
fast=7->next=1
1!=NULL
slow=5->next=4
fast=1->next=NULL
iteration 2:
fast==NULL
so iteration stops
split1=6(head)
split2=slow->next=4->next=7
slow->next=NULL
thus the partitioned linked lists are
split1=6->5->4->NULL
split2=7->1->NULL
----------------------------------------------------------------

Now we individually sort split1 & split2 recursively
Thus needless to say it again partitions 
both the list until base cases is reached. 
The ultimate outcome is the two sorted list
Split1 pointing to 4->5->6->NULL
Split2 pointing to 1->7->NULL
----------------------------------------------------------------

Now we merge this two sorted list to produce the ultimate sorted list
mergeList(split1, split2) // mergeList(4, 1)
Split1!=NULL
Split2!=NULL
Split1->data>split2->data (4>1)   
Thus newhead =split2 // newhead =1
newhead->next=mergeList(split1, split2->next));
Call  mergeList(split1, split2->next) // (4, 7)
----------------------------------------------------------------

mergeList( split1, split2) //mergeList(4,7)
Split1!=NULL
Split2!=NULL
Split1->data<split2->data (4<7)   
Thus newhead =split1 // newhead =4
newhead->next=mergeList(split1->next, split2));
Call  mergeList(split1->next, split2) // (5, 7)
----------------------------------------------------------------

mergeList( split1, split2) //mergeList(5,7)
Split1!=NULL
Split2!=NULL
Split1->data<split2->data (5<7)   
Thus newhead =split1 // newhead =5
newhead->next=mergeList(split1->next, split2));
Call  mergeList(split1->next, split2) // (6, 7)
----------------------------------------------------------------

mergeList( split1, split2) //mergeList(6,7)
Split1!=NULL
Split2!=NULL
Split1->data<split2->data (6<7)   
Thus newhead =split1 // newhead =6
newhead->next=mergeList(split1->next, split2));
Call  mergeList(split1->next, split2) // (NULL, 7)
----------------------------------------------------------------

mergeList( split1, split2) //mergeList(5,7)
Split1==NULL
Return split2 (7->NULL)
----------------------------------------------------------------

Thus at mergeList(6,7)
newhead=6
newhead->next=7->NULL
function returns 6->7->NULL
----------------------------------------------------------------

Thus at mergeList(5,7)
newhead=5
newhead->next=6->7->NULL
function returns 5->6->7->NULL
----------------------------------------------------------------

Thus at mergeList(4,7)
newhead=4
newhead->next=5->6->7->NULL
function returns 4->5->6->7->NULL
----------------------------------------------------------------

Thus at mergeList(4,1)
newhead=1
newhead->next=4->5->6->7->NULL
function returns 1->4->5->6->7->NULL
Which is the sorted list