Merge Sort Explanation with Example

Last Updated on February 2, 2023 by Prepbytes

In this article, we are going to discuss merge sort and how to merge k sorted lists.

Merge Sort

• Merge sort is a divide-and-conquer algorithm.
• It is a recursive algorithm.
• In merge sort, we have to divide the container (container can be an array, list, etc.) into two halves then we will call merge sort recursively on the two halves.
• These two merge sort calls return sorted containers, and we then, merge these sorted containers in such a way that the whole container remains sorted.
• Have a look at the below image to see in a nutshell how merge sort works.

Merge sort example:-

Now, we have a brief understanding of the merge sort algorithm.

How to Merge K Sorted Linked Lists

But before learning how to merge k sorted linked lists, we have to first know how to merge two sorted linked lists.

Merging two sorted linked list Algorithm:
When the two recursive call will return the two sorted list, then we will merge those sorted list into a single list using these below steps.

1. Initialize two pointer variable named curr1 and curr2 with left sorted sub-list and right sorted sub-list.
2. Initialize two pointer variable named si and ei with NULL, these two pointer variables are head and tail of the final sorted linked list.
3. If the data of curr1 is less than the data of curr2, then, store curr1 in next of ei & move curr1 to the next of curr1.
4. Else, if the data of curr2 is less than curr1, then store curr2 in next of ei & move curr2 to the next of curr2.
5. Repeat steps 3 and 4 until either the curr1 or curr2 is not equal to null.
6. Now add any remaining nodes of the first or the second linked list to the merged linked list.
7. Return the head of the merged sorted linked list containing all the nodes of the two sorted sub-lists.

We are given k linked lists each of length n. Each given linked list is sorted in non-decreasing order, Our task is to merge them into a single sorted (non-decreasing order) linked list and print the sorted linked list as output.

Examples:
Input:

k = 3, n =  3
list1 = 1->3->5->NULL
list2 = 2->4->8->NULL
list3 = 6->7->9->NULL

Output:

1->2->3->4->5->6->7->8->9->NULL

Input:

k = 2, n = 4
list1 = 2->3->10->12->NULL
list2 = 1->4->8->9->NULL

Output:

1->2->3->4->8->9->10->12->NULL

Brief about Min-Heap

Min-heap is a min priority queue. It is a complete binary tree having a root value smaller than both children’s values.

           2
         /   \
        4     5
       / \  
      11  6  

    Min-Heap

We will use a min-heap to get the current minimum value node of linked lists.

Approach:

The main intuition behind this approach is to maintain the current smallest element from all given linked lists and add that element i.e Node to the final linked list. Let’s understand the algorithm step-wise.

Before understanding the algorithm let’s go briefly through the min-heap data structure. Min-heap data structure is a type of data structure that has the smallest element among all elements in the heap on the top.

Algorithm:

Create a min-heap of type Node because it will store the nodes of the linked list. First of all, insert the first node of all the ‘k’ linked lists.

Continue these following steps until the min-heap is not empty:-

• Remove the top element of the min-heap (that is the current minimum element in the min-heap).
• Add this node to the result list.
• Push the next node (if exists) of the node (that is popped out from min heap in step1) in the min-heap.

Finally, the sorted linked list is ready. Return the head node of the merged list.

Code:

#include <bits/stdc++.h>
using namespace std;
 
struct Node{
  int data;
  struct Node* next;
};
 
//function to create a new node
struct Node* newNodeInsert(int data){
  // Allocate Node
  struct Node* new_node = new Node();
 
  // assigning data of the node
  new_node->data = data;
  new_node->next = NULL;
 
  return new_node;
}
 
// 'compare' function used to build up the heap of type min-heap
struct compare{
  bool operator()(struct Node* a, struct Node* b){
    return a->data > b->data;
  }
};
 
// Function to merge k sorted linked lists
struct Node* mergeKSortedLists(struct Node* lists[], int k){
  priority_queue<Node*, vector<Node*>, compare> pq;
  //min heap of type pq
 
  // Push the head nodes of all the k lists in 'pq' i.e min-heap
  for (int i = 0; i < k; i++){
    if (lists[i] != NULL){
      pq.push(lists[i]);
    }
  }
  
  struct Node *ansHead = NULL;
  struct Node *ansTail = NULL;
  
  // continue until 'pq' is not empty
  while (!pq.empty()){
    // Get the top element of min heap
    // that's the smallest value node 
    struct Node* curr = pq.top();
    pq.pop();
 
    // Add that node to ans list
    if(ansHead == NULL){
    ansHead = curr;
    ansTail = ansHead;
    }else{
    ansTail->next = curr;
    ansTail = ansTail->next;
    }
    // push the next node of the curr->next in the min heap (if exists)
    if (curr->next != NULL)
    pq.push(curr->next);
  }
 
  // Address of head node of the required
  // merged list
  return ansHead->next;
}
 
// function to print the singly
// linked list
void printList(struct Node* head){
  while (head != NULL){
    cout << head->data << " ";
    head = head->next;
  }
  return;
}
 
 
int main(){
  // k is the number of the linked lists and n is the length of the linked list
  int k = 3, n = 4;
 
  // lists is array of Node pointer pointing towards head of the linked lists
  Node* lists[k];
 
  // Creating k = 3 sorted lists
  lists[0] = newNodeInsert(1);
  lists[0]->next = newNodeInsert(3);
  lists[0]->next->next = newNodeInsert(5);
 
  lists[1] = newNodeInsert(2);
  lists[1]->next = newNodeInsert(4);
  lists[1]->next->next = newNodeInsert(8);
 
  lists[2] = newNodeInsert(6);
  lists[2]->next = newNodeInsert(7);
  lists[2]->next->next = newNodeInsert(9);
 
  // Merge the k sorted lists
  struct Node* ans = mergeKSortedLists(lists, k);
 
 
  // Print the final merged list
  printList(ans);
}
 
 

Input:

k = 3, n =  3
list1 = 1->3->5->NULL
list2 = 2->4->8->NULL
list3 = 6->7->9->NULL

Output:

1->2->3->4->5->6->7->8->9->NULL

Dry Run:

And the above processes will continue like that until the min-heap is empty.

Time Complexity: O(n k log k)
Insertion and deletion in a min-heap require log k time. This process will continue for n* k nodes.

Auxiliary Space: O(k).
The min-heap will have the atmost ‘k’ number of elements at any point in time.