Lecture 142:- Sort List Using Merge Sort

To sort a linked list using the merge sort algorithm, you can follow these steps:

1. Divide the linked list into two halves.
2. Recursively sort each half using merge sort.
3. Merge the sorted halves to obtain the final sorted linked list.

Here's a C++ implementation of the merge sort algorithm for a singly linked list:

cppCopy code

#include <iostream> class Node { public: int data; Node* next; Node(int value) : data(value), next(nullptr) {} }; Node* merge(Node* left, Node* right) { if (!left) return right; if (!right) return left; Node* merged = nullptr; if (left->data <= right->data) { merged = left; merged->next = merge(left->next, right); } else { merged = right; merged->next = merge(left, right->next); } return merged; } Node* mergeSort(Node* head) { if (!head || !head->next) return head; Node* middle = head; Node* fast = head->next; while (fast && fast->next) { middle = middle->next; fast = fast->next->next; } Node* left = head; Node* right = middle->next; middle->next = nullptr; left = mergeSort(left); right = mergeSort(right); return merge(left, right); } void displayList(Node* head) { while (head) { std::cout << head->data << " "; head = head->next; } std::cout << std::endl; } int main() { Node* head = new Node(3); head->next = new Node(1); head->next->next = new Node(4); head->next->next->next = new Node(2); std::cout << "Original List: "; displayList(head); head = mergeSort(head); std::cout << "Sorted List: "; displayList(head); return 0; }

In this implementation, the merge function merges two sorted linked lists. The mergeSort function divides the list into two halves and recursively sorts them using merge sort. Finally, the sorted halves are merged back together.

The time complexity of merge sort for a linked list is O(n log n), where n is the number of nodes in the list.