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).
The illustration below shows this algorithm:
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 nodeclass node {public:int data;node* next;};// Merging two sorted lists.node* MergeSortedList(node* lst1, node* lst2){node* result = NULL;// Base Casesif (lst1 == NULL)return (lst2);else if (lst2 == NULL)return (lst1);// recursively merging two listsif (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 Sortvoid MergeSort(node** thead){node* head = *thead;node* ptr1;node* ptr2;// Base Caseif ((head == NULL) || (head->next == NULL)) {return;}// Splitting listSplitList(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 listnode* res = NULL;node* MyList = NULL;// List: 10->4->15->1->2->12->54push(&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