Merge Sort for Linked Lists Last Updated : 19 Sep, 2024 Summarize Suggest changes Share Like Article Like Report Given a singly linked list, The task is to sort the linked list in non-decreasing order using merge sort.Examples: Input: 40 -> 20 -> 60 -> 10 -> 50 -> 30 -> NULLOutput: 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> NULLInput: 9 -> 5 -> 2 -> 8 -> NULLOutput: 2 -> 5 -> 8 -> 9 -> NULL Approach:The prerequisite for this problem is Merge Sort. Here we have to maintain a MergeSort function that sorts the list in three steps:Split the List into Two Halves: Use two pointers, fast and slow, starting at the head. Move fast two steps and slow one step. When fast reaches the end, slow is at the midpoint. Split the list into two halves: the first half from head to just before slow, and the second from slow->next to the end. Set slow->next to NULL.Apply MergeSort Recursively: Recursively call MergeSort() on both halves. The base case is when the list is empty (head == NULL) or has one node (head->next == NULL), in which case return the list as is.Merge the Two Sorted Halves: After sorting both halves, call merge() to merge them by comparing nodes and linking accordingly. Append any remaining nodes from the exhausted half. Finally, returns the new head of the sorted list. C++ // C++ program for merge sort on singly linked list #include <iostream> using namespace std; class Node { public: int data; Node *next; Node(int x) { data = x; next = nullptr; } }; // Function to split the singly linked list into two halves Node *split(Node *head) { Node *fast = head; Node *slow = head; // Move fast pointer two steps and slow pointer // one step until fast reaches the end while (fast != nullptr && fast->next != nullptr) { fast = fast->next->next; if (fast != nullptr) { slow = slow->next; } } // Split the list into two halves Node *temp = slow->next; slow->next = nullptr; return temp; } // Function to merge two sorted singly linked lists Node *merge(Node *first, Node *second) { // If either list is empty, return the other list if (first == nullptr) return second; if (second == nullptr) return first; // Pick the smaller value between first and second nodes if (first->data < second->data) { // Recursively merge the rest of the lists and // link the result to the current node first->next = merge(first->next, second); return first; } else { // Recursively merge the rest of the lists // and link the result to the current node second->next = merge(first, second->next); return second; } } // Function to perform merge sort on a singly linked list Node *MergeSort(Node *head) { // Base case: if the list is empty or has only one node, // it's already sorted if (head == nullptr || head->next == nullptr) return head; // Split the list into two halves Node *second = split(head); // Recursively sort each half head = MergeSort(head); second = MergeSort(second); // Merge the two sorted halves return merge(head, second); } void printList(Node *head) { Node *curr = head; while (curr != nullptr) { cout << curr->data << " "; curr = curr->next; } cout << endl; } int main() { // Create a hard-coded singly linked list: // 9 -> 8 -> 5 -> 2 Node *head = new Node(9); head->next = new Node(8); head->next->next = new Node(5); head->next->next->next = new Node(2); head = MergeSort(head); printList(head); return 0; } C // C program for merge sort on singly linked list #include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node* next; }; // Function to split the singly linked list into two halves struct Node* split(struct Node* head) { struct Node* fast = head; struct Node* slow = head; // Move fast pointer two steps and slow pointer // one step until fast reaches the end while (fast != NULL && fast->next != NULL) { fast = fast->next->next; if (fast != NULL) { slow = slow->next; } } // Split the list into two halves struct Node* temp = slow->next; slow->next = NULL; return temp; } // Function to merge two sorted singly linked lists struct Node* merge(struct Node* first, struct Node* second) { // If either list is empty, return the other list if (first == NULL) return second; if (second == NULL) return first; // Pick the smaller value between first and second nodes if (first->data < second->data) { // Recursively merge the rest of the lists and // link the result to the current node first->next = merge(first->next, second); return first; } else { // Recursively merge the rest of the lists // and link the result to the current node second->next = merge(first, second->next); return second; } } // Function to perform merge sort on a singly linked list struct Node* MergeSort(struct Node* head) { // Base case: if the list is empty or has only one node, // it's already sorted if (head == NULL || head->next == NULL) { return head; } // Split the list into two halves struct Node* second = split(head); // Recursively sort each half head = MergeSort(head); second = MergeSort(second); // Merge the two sorted halves return merge(head, second); } void printList(struct Node* head) { struct Node* curr = head; while (curr != NULL) { printf("%d ", curr->data); curr = curr->next; } printf("\n"); } // Function to create a new node struct Node* createNode(int x) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = x; newNode->next = NULL; return newNode; } int main() { // Create a hard-coded singly linked list: // 9 -> 8 -> 5 -> 2 struct Node* head = createNode(9); head->next = createNode(8); head->next->next = createNode(5); head->next->next->next = createNode(2); head = MergeSort(head); printList(head); return 0; } Java // Java program for merge sort on singly linked list class Node { int data; Node next; Node(int x) { data = x; next = null; } } // Function to split the singly linked list into two halves class GfG { static Node split(Node head) { Node fast = head; Node slow = head; // Move fast pointer two steps and slow pointer // one step until fast reaches the end while (fast != null && fast.next != null) { fast = fast.next.next; if (fast != null) { slow = slow.next; } } // Split the list into two halves Node temp = slow.next; slow.next = null; return temp; } // Function to merge two sorted singly linked lists static Node merge(Node first, Node second) { // If either list is empty, return the other list if (first == null) return second; if (second == null) return first; // Pick the smaller value between first and second nodes if (first.data < second.data) { // Recursively merge the rest of the lists and // link the result to the current node first.next = merge(first.next, second); return first; } else { // Recursively merge the rest of the lists // and link the result to the current node second.next = merge(first, second.next); return second; } } // Function to perform merge sort on a singly linked list static Node mergeSort(Node head) { // Base case: if the list is empty or has only one node, // it's already sorted if (head == null || head.next == null) { return head; } // Split the list into two halves Node second = split(head); // Recursively sort each half head = mergeSort(head); second = mergeSort(second); // Merge the two sorted halves return merge(head, second); } static void printList(Node head) { Node curr = head; while (curr != null) { System.out.print(curr.data + " "); curr = curr.next; } System.out.println(); } public static void main(String[] args) { // Create a hard-coded singly linked list: // 9 -> 8 -> 5 -> 2 Node head = new Node(9); head.next = new Node(8); head.next.next = new Node(5); head.next.next.next = new Node(2); head = mergeSort(head); printList(head); } } Python # Python program for merge sort on singly linked list class Node: def __init__(self, x): self.data = x self.next = None def split(head): fast = head slow = head # Move fast pointer two steps and slow pointer # one step until fast reaches the end while fast and fast.next: fast = fast.next.next if fast: slow = slow.next # Split the list into two halves second = slow.next slow.next = None return second def merge(first, second): # If either list is empty, return the other list if not first: return second if not second: return first # Pick the smaller value between first and second nodes if first.data < second.data: first.next = merge(first.next, second) return first else: second.next = merge(first, second.next) return second def merge_sort(head): # Base case: if the list is empty or has only one node, # it's already sorted if not head or not head.next: return head # Split the list into two halves second = split(head) # Recursively sort each half head = merge_sort(head) second = merge_sort(second) # Merge the two sorted halves return merge(head, second) def print_list(head): curr = head while curr: print(curr.data, end=" ") curr = curr.next print() if __name__ == "__main__": # Create a hard-coded singly linked list: # 9 -> 8 -> 5 -> 2 head = Node(9) head.next = Node(8) head.next.next = Node(5) head.next.next.next = Node(2) head = merge_sort(head) print_list(head) C# // C# program for merge sort on singly linked list using System; class Node { public int data; public Node next; public Node(int x) { data = x; next = null; } } // Function to split the singly linked list into two halves class GfG { static Node Split(Node head) { Node fast = head; Node slow = head; // Move fast pointer two steps and slow pointer // one step until fast reaches the end while (fast != null && fast.next != null) { fast = fast.next.next; if (fast != null) { slow = slow.next; } } // Split the list into two halves Node temp = slow.next; slow.next = null; return temp; } // Function to merge two sorted singly linked lists static Node Merge(Node first, Node second) { // If either list is empty, return the other list if (first == null) return second; if (second == null) return first; // Pick the smaller value between first and second // nodes if (first.data < second.data) { // Recursively merge the rest of the lists and // link the result to the current node first.next = Merge(first.next, second); return first; } else { // Recursively merge the rest of the lists // and link the result to the current node second.next = Merge(first, second.next); return second; } } // Function to perform merge sort on a singly linked // list static Node MergeSort(Node head) { // Base case: if the list is empty or has only one // node, it's already sorted if (head == null || head.next == null) return head; // Split the list into two halves Node second = Split(head); // Recursively sort each half head = MergeSort(head); second = MergeSort(second); // Merge the two sorted halves return Merge(head, second); } static void PrintList(Node head) { Node curr = head; while (curr != null) { Console.Write(curr.data + " "); curr = curr.next; } Console.WriteLine(); } public static void Main() { // Create a hard-coded singly linked list: // 9 -> 8 -> 5 -> 2 Node head = new Node(9); head.next = new Node(8); head.next.next = new Node(5); head.next.next.next = new Node(2); head = MergeSort(head); PrintList(head); } } JavaScript // JavaScript program for merge sort on singly linked list class Node { constructor(x) { this.data = x; this.next = null; } } // Function to split the singly linked list into two halves function split(head) { let fast = head; let slow = head; // Move fast pointer two steps and slow pointer // one step until fast reaches the end while (fast && fast.next) { fast = fast.next.next; if (fast) { slow = slow.next; } } // Split the list into two halves let second = slow.next; slow.next = null; return second; } // Function to merge two sorted singly linked lists function merge(first, second) { // If either list is empty, return the other list if (!first) return second; if (!second) return first; // Pick the smaller value between first and second nodes if (first.data < second.data) { first.next = merge(first.next, second); return first; } else { second.next = merge(first, second.next); return second; } } // Function to perform merge sort on a singly linked list function mergeSort(head) { // Base case: if the list is empty or has only one node, // it's already sorted if (!head || !head.next) return head; // Split the list into two halves let second = split(head); // Recursively sort each half head = mergeSort(head); second = mergeSort(second); // Merge the two sorted halves return merge(head, second); } function printList(head) { let curr = head; while (curr) { console.log(curr.data + " "); curr = curr.next; } console.log(); } // Create a hard-coded singly linked list: // 9 -> 8 -> 5 -> 2 let head = new Node(9); head.next = new Node(8); head.next.next = new Node(5); head.next.next.next = new Node(2); head = mergeSort(head); printList(head); Output2 5 8 9 Time Complexity: O(n*log(n))Auxiliary Space: O(logn) Advertise with us Next Article Merge Sort for Doubly Linked List K kartik Follow Similar Reads Merge Sort - Data Structure and Algorithms Tutorials Merge sort is a popular sorting algorithm known for its efficiency and stability. It follows the divide-and-conquer approach. It works by recursively dividing the input array into two halves, recursively sorting the two halves and finally merging them back together to obtain the sorted array. Merge 14 min read Merge sort in different languagesC Program for Merge SortMerge Sort is a comparison-based sorting algorithm that works by dividing the input array into two halves, then calling itself for these two halves, and finally it merges the two sorted halves. In this article, we will learn how to implement merge sort in C language.What is Merge Sort Algorithm?Merg 3 min read C++ Program For Merge SortMerge Sort is a comparison-based sorting algorithm that uses divide and conquer paradigm to sort the given dataset. It divides the dataset into two halves, calls itself for these two halves, and then it merges the two sorted halves.In this article, we will learn how to implement merge sort in a C++ 4 min read Java Program for Merge SortMerge Sort is a divide-and-conquer algorithm. It divides the input array into two halves, calls itself the two halves, and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, l, m, r) is a key process that assumes that arr[l..m] and arr[m+1..r] are 3 min read Merge Sort in PythonMerge Sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, l, m, r) is key process that assumes that arr[l..m] and arr[m+1..r] are sorte 4 min read Merge Sort using Multi-threadingMerge Sort is a popular sorting technique which divides an array or list into two halves and then start merging them when sufficient depth is reached. Time complexity of merge sort is O(nlogn).Threads are lightweight processes and threads shares with other threads their code section, data section an 14 min read Variations of Merge Sort3-way Merge SortMerge Sort is a divide-and-conquer algorithm that recursively splits an array into two halves, sorts each half, and then merges them. A variation of this is 3-way Merge Sort, where instead of splitting the array into two parts, we divide it into three equal parts. In traditional Merge Sort, the arra 13 min read Iterative Merge SortGiven an array of size n, the task is to sort the given array using iterative merge sort.Examples:Input: arr[] = [4, 1, 3, 9, 7]Output: [1, 3, 4, 7, 9]Explanation: The output array is sorted.Input: arr[] = [1, 3 , 2]Output: [1, 2, 3]Explanation: The output array is sorted.You can refer to Merge Sort 9 min read In-Place Merge SortImplement Merge Sort i.e. standard implementation keeping the sorting algorithm as in-place. In-place means it does not occupy extra memory for merge operation as in the standard case. Examples: Input: arr[] = {2, 3, 4, 1} Output: 1 2 3 4 Input: arr[] = {56, 2, 45} Output: 2 45 56 Approach 1: Mainta 15+ min read In-Place Merge Sort | Set 2Given an array A[] of size N, the task is to sort the array in increasing order using In-Place Merge Sort. Examples: Input: A = {5, 6, 3, 2, 1, 6, 7}Output: {1, 2, 3, 5, 6, 6, 7} Input: A = {2, 3, 4, 1}Output: {1, 2, 3, 4} Approach: The idea is to use the inplace_merge() function to merge the sorted 7 min read Merge Sort with O(1) extra space merge and O(n log n) time [Unsigned Integers Only]We have discussed Merge sort. How to modify the algorithm so that merge works in O(1) extra space and algorithm still works in O(n Log n) time. We may assume that the input values are integers only. Examples: Input : 5 4 3 2 1 Output : 1 2 3 4 5 Input : 999 612 589 856 56 945 243 Output : 56 243 589 10 min read Merge Sort in Linked ListMerge Sort for Linked ListsGiven a singly linked list, The task is to sort the linked list in non-decreasing order using merge sort.Examples: Input: 40 -> 20 -> 60 -> 10 -> 50 -> 30 -> NULLOutput: 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> NULLInput: 9 -> 5 -> 2 -> 8 -> NULLOutput: 2 - 12 min read Merge Sort for Doubly Linked ListGiven a doubly linked list, The task is to sort the doubly linked list in non-decreasing order using merge sort.Examples:Input: 10 <-> 8 <-> 4 <-> 2Output: 2 <-> 4 <-> 8 <-> 10Input: 5 <-> 3 <-> 2Output: 2 <-> 3 <-> 5 Note: Merge sort for a 13 min read Iterative Merge Sort for Linked ListGiven a singly linked list of integers, the task is to sort it using iterative merge sort.Examples:Input: 40 -> 20 -> 60 -> 10 -> 50 -> 30 -> NULLOutput: 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> NULLInput: 9 -> 5 -> 2 -> 8 -> NULLOutput: 2 -> 5 -> 8 - 13 min read Merge two sorted lists (in-place)Given two sorted linked lists consisting of n and m nodes respectively. The task is to merge both of the lists and return the head of the merged list.Example:Input: Output: Input: Output: Approach:The idea is to iteratively merge two sorted linked lists using a dummy node to simplify the process. A 9 min read Merge K sorted Doubly Linked List in Sorted OrderGiven K sorted doubly linked list. The task is to merge all sorted doubly linked list in single sorted doubly linked list means final list must be sorted.Examples: Input: List 1 : 2 <-> 7 <-> 8 <-> 12 <-> 15 <-> NULL List 2 : 4 <-> 9 <-> 10 <-> NULL Li 15+ min read Merge a linked list into another linked list at alternate positionsGiven two singly linked lists, The task is to insert nodes of the second list into the first list at alternate positions of the first list and leave the remaining nodes of the second list if it is longer.Example:Input: head1: 1->2->3 , head2: 4->5->6->7->8Output: head1: 1->4- 8 min read Find a permutation that causes worst case of Merge Sort Given a set of elements, find which permutation of these elements would result in worst case of Merge Sort.Asymptotically, merge sort always takes O(n Log n) time, but the cases that require more comparisons generally take more time in practice. We basically need to find a permutation of input eleme 12 min read How to make Mergesort to perform O(n) comparisons in best case? As we know, Mergesort is a divide and conquer algorithm that splits the array to halves recursively until it reaches an array of the size of 1, and after that it merges sorted subarrays until the original array is fully sorted. Typical implementation of merge sort works in O(n Log n) time in all thr 3 min read Concurrent Merge Sort in Shared Memory Given a number 'n' and a n numbers, sort the numbers using Concurrent Merge Sort. (Hint: Try to use shmget, shmat system calls).Part1: The algorithm (HOW?) Recursively make two child processes, one for the left half, one of the right half. If the number of elements in the array for a process is less 10 min read Visualization of Merge SortSorting Algorithm Visualization : Merge SortThe human brain can easily process visuals instead of long codes to understand the algorithms. In this article, a program that program visualizes the Merge sort Algorithm has been implemented. The GUI(Graphical User Interface) is implemented using pygame package in python. Approach: An array of rand 3 min read Merge Sort Visualization in JavaScriptGUI(Graphical User Interface) helps users with better understanding programs. In this article, we will visualize Merge Sort using JavaScript. We will see how the arrays are divided and merged after sorting to get the final sorted array. Refer: Merge SortCanvas in HTMLAsynchronous Function in JavaSc 4 min read Visualize Merge sort Using Tkinter in PythonPrerequisites: Python GUI – tkinter In this article, we will create a GUI application that will help us to visualize the algorithm of merge sort using Tkinter in Python. Merge Sort is a popular sorting algorithm. It has a time complexity of N(logN) which is faster than other sorting algorithms like 5 min read Visualization of Merge sort using MatplotlibPrerequisites: Introduction to Matplotlib, Merge Sort Visualizing algorithms makes it easier to understand them by analyzing and comparing the number of operations that took place to compare and swap the elements. For this we will use matplotlib, to plot bar graphs to represent the elements of the a 3 min read 3D Visualisation of Merge Sort using MatplotlibVisualizing algorithms makes it easier to understand them by analyzing and comparing the number of operations that took place to compare and swap the elements. 3D visualization of algorithms is less common, for this we will use matplotlib to plot bar graphs and animate them to represent the elements 3 min read Some problems on Merge SortCount Inversions of an ArrayGiven an integer array arr[] of size n, find the inversion count in the array. Two array elements arr[i] and arr[j] form an inversion if arr[i] > arr[j] and i < j.Note: Inversion Count for an array indicates that how far (or close) the array is from being sorted. If the array is already sorted 15+ min read Count of smaller elements on right side of each element in an Array using Merge sortGiven an array arr[] of N integers, the task is to count the number of smaller elements on the right side for each of the element in the array Examples: Input: arr[] = {6, 3, 7, 2} Output: 2, 1, 1, 0 Explanation: Smaller elements after 6 = 2 [3, 2] Smaller elements after 3 = 1 [2] Smaller elements a 12 min read Sort a nearly sorted (or K sorted) arrayGiven an array arr[] and a number k . The array is sorted in a way that every element is at max k distance away from it sorted position. It means if we completely sort the array, then the index of the element can go from i - k to i + k where i is index in the given array. Our task is to completely s 6 min read Median of two Sorted Arrays of Different SizesGiven two sorted arrays, a[] and b[], the task is to find the median of these sorted arrays. Assume that the two sorted arrays are merged and then median is selected from the combined array.This is an extension of Median of two sorted arrays of equal size problem. Here we handle arrays of unequal si 15+ min read Merge k Sorted ArraysGiven K sorted arrays, merge them and print the sorted output.Examples:Input: K = 3, arr = { {1, 3, 5, 7}, {2, 4, 6, 8}, {0, 9, 10, 11}}Output: 0 1 2 3 4 5 6 7 8 9 10 11 Input: k = 4, arr = { {1}, {2, 4}, {3, 7, 9, 11}, {13} }Output: 1 2 3 4 7 9 11 13Table of ContentNaive - Concatenate all and SortU 15+ min read Merge K sorted arrays of different sizes | ( Divide and Conquer Approach )Given k sorted arrays of different length, merge them into a single array such that the merged array is also sorted.Examples: Input : {{3, 13}, {8, 10, 11} {9, 15}} Output : {3, 8, 9, 10, 11, 13, 15} Input : {{1, 5}, {2, 3, 4}} Output : {1, 2, 3, 4, 5} Let S be the total number of elements in all th 8 min read Merge K sorted linked listsGiven k sorted linked lists of different sizes, the task is to merge them all maintaining their sorted order.Examples: Input: Output: Merged lists in a sorted order where every element is greater than the previous element.Input: Output: Merged lists in a sorted order where every element is greater t 15+ min read Union and Intersection of two Linked List using Merge SortGiven two singly Linked Lists, create union and intersection lists that contain the union and intersection of the elements present in the given lists. Each of the two lists contains distinct node values.Note: The order of elements in output lists doesn't matter.Examples:Input: head1: 10 -> 15 - 15+ min read Sorting by combining Insertion Sort and Merge Sort algorithmsInsertion sort: The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.Advantages: Following are the advantages of insertion sort: If the size of the list to be sorted is small, insertion sort ru 2 min read Find array with k number of merge sort callsGiven two numbers n and k, find an array containing values in [1, n] and requires exactly k calls of recursive merge sort function. Examples: Input : n = 3 k = 3 Output : a[] = {2, 1, 3} Explanation: Here, a[] = {2, 1, 3} First of all, mergesort(0, 3) will be called, which then sets mid = 1 and call 6 min read Difference of two Linked Lists using Merge sortGiven two Linked List, the task is to create a Linked List to store the difference of Linked List 1 with Linked List 2, i.e. the elements present in List 1 but not in List 2.Examples: Input: List1: 10 -> 15 -> 4 ->20, List2: 8 -> 4 -> 2 -> 10 Output: 15 -> 20 Explanation: In the 14 min read Article Tags : Linked List Sorting DSA Microsoft Adobe Paytm Accolite MAQ Software Veritas Merge Sort Linked-List-Sorting +7 More Practice Tags : AccoliteAdobeMAQ SoftwareMicrosoftPaytmVeritasLinked ListMerge SortSorting +5 More Like