C++ Programming Code Examples C++ > Sorting Searching Code Examples Program to Implement Merge Sort using Linked List Program to Implement Merge Sort using Linked List This is a C++ program to sort the given data using Merge Sort using linked list. - Merge-sort is based on an algorithmic design pattern called divide-and-conquer. - It forms tree structure. - The height of the tree will be log(n). - we merge n element at every level of the tree. - The time complexity of this algorithm is O(n*log(n)). - Split the data into two equal half until we get at most one element in both half. - Merge Both into one making sure the resulting sequence is sorted. - Recursively split them and merge on the basis of constraint given in step 1. - Display the result. - Exit. #include<iostream> using namespace std; // A structure representing a node of a linked list. struct node { int data; node *next; }; // A function creating a new node. node* NewNode(int d) { struct node *temp = new node; temp->data = d; temp->next = NULL; // Returning temp as the new node. return temp; } // A function adding the given data at the end of the linked list. node* AddToList(node *tail, int data) { struct node *newnode; newnode = NewNode(data); if(tail == NULL) { tail = newnode; } // If tail is not null assign newnode to the next of tail. else { tail->next = newnode; // Shift tail pointer to the added node. tail = tail->next; } return tail; } node* Merge(node* h1, node* h2) { node *t1 = new node; node *t2 = new node; node *temp = new node; // Return if the first list is empty. if(h1 == NULL) return h2; // Return if the Second list is empty. if(h2 == NULL) return h1; t1 = h1; // A loop to traverse the second list, to merge the nodes to h1 in sorted way. while (h2 != NULL) { // Taking head node of second list as t2. t2 = h2; // Shifting second list head to the next. h2 = h2->next; t2->next = NULL; // If the data value is lesser than the head of first list add that node at the beginning. if(h1->data > t2->data) { t2->next = h1; h1 = t2; t1 = h1; continue; } // Traverse the first list. flag: if(t1->next == NULL) { t1->next = t2; t1 = t1->next; } // Traverse first list until t2->data more than node's data. else if((t1->next)->data <= t2->data) { t1 = t1->next; goto flag; } else { // Insert the node as t2->data is lesser than the next node. temp = t1->next; t1->next = t2; t2->next = temp; } } // Return the head of new sorted list. return h1; } // A function implementing Merge Sort on linked list using reference. void MergeSort(node **head) { node *first = new node; node *second = new node; node *temp = new node; first = *head; temp = *head; // Return if list have less than two nodes. if(first == NULL || first->next == NULL) { return; } else { // Break the list into two half as first and second as head of list. while(first->next != NULL) { first = first->next; if(first->next != NULL) { temp = temp->next; first = first->next; } } second = temp->next; temp->next = NULL; first = *head; } // Implementing divide and conquer approach. MergeSort(&first); MergeSort(&second); // Merge the two part of the list into a sorted one. *head = Merge(first, second); } int main() { int n, i, num; struct node *head = new node; struct node *tail = new node; head = NULL; tail = NULL; cout<<"\nEnter the number of data element to be sorted: "; cin>>n; // Create linked list. for(i = 0; i < n; i++) { cout<<"Enter element "<<i+1<<": "; cin>>num; tail = AddToList(tail, num); if(head == NULL) head = tail; } // Send reference of head into MergeSort(). MergeSort(&head); // Printing the sorted data. cout<<"\nSorted Data "; while(head != NULL) { cout<<".."<<head->data; head=head->next; } return 0; }