Example: 3 -> 4 -> 5-> 1 -> 2 Output: 1 -> 2 -> 3 -> 4 -> 5
Merge sort is a divide and conquer algorithm.
Here we divide the elements into smaller parts, then while merging them, we merge according to sorted order.
Example:
Consider below elements, we start dividing exactly half of the array.
Input: 3, 4, 1, 2, 9, 7, 8, 5
Divide: 3, 4, 1, 2, 9, 7, 8, 5
Divide: 3, 4, 1, 2, 9, 7, 8, 5
Merge: 3, 4, 1, 2 7, 9 5, 8
Merge: 1, 2, 3, 4, 5, 7, 8, 9
Merge: 1, 2, 3, 4, 5, 7, 8, 9
In similar way, we divide the given linked list and then merge them to get the desired result.
To achieve, we need to make use of recursion algorithm.
Solution in C++
#include<iostream> #include<vector> #include<string> using namespace std; struct Node { int data; Node *next; Node(int x) { data = x; next = NULL; } }; void print_list(Node *head) { Node *start = head; while(start) { cout<<start->data<<" -> "; start = start->next; } cout<<"\n"; } Node* merge_nodes(Node* l1, Node* l2) { Node helper_node(0); Node* cur = &helper_node; // add elements at their respective postion while (l1 != NULL && l2 != NULL) { if (l1->data < l2->data) { cur->next = l1; l1 = l1->next; } else { cur->next = l2; l2 = l2->next; } cur = cur->next; } // if any one of the list is empty and other list has elements in it, // add them appropriately if (l1 != NULL) cur->next = l1; else cur->next = l2; return helper_node.next; } Node* sort_list(Node* head) { if (head == NULL || head->next == NULL) return head; Node* slow = head; Node* fast = head->next; // get the middle of the list while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; } //"fast" will hold the start of 2nd half fast = slow->next; slow->next = NULL; // call recursively "sort_list", when all the nodes are divided, // call "merge_nodes" functions to merge all the divided nodes. return merge_nodes(sort_list(head), sort_list(fast)); } int main() { Node *head = new Node(2); head -> next = new Node(1); head -> next -> next = new Node(4); head -> next -> next -> next = new Node(3); head -> next -> next -> next -> next = new Node(6); head -> next -> next -> next -> next -> next = new Node(5); head -> next -> next -> next -> next -> next -> next = new Node(8); cout<<"The original list = "<<endl; print_list(head); cout<<"Sorting the list ... "<<endl;; Node *new_head = sort_list(head); cout<<"\nAfter sorting: "<<endl; print_list(new_head); return 0; }
Output:
The original list = 2 -> 1 -> 4 -> 3 -> 6 -> 5 -> 8 -> Sorting the list ... After sorting: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 8 ->