Skip to main content

Merge sort a linked list

Sorting a linked list is much more complex than sorting an array. Because you need to be wary of links at each step and update them.

The most convenient ways of sorting a linked list is insertion sort, where in you remove one node at a time from list and insert them to the sorted list in correct position.

But merge sorting a linked list uses another approach. It splits the list into two halves, sorts them recursively and then merges them maintaining ascending order of key values.

So the three basic parts of this approach are
  1. Splitting the list into two halves of equal length
  2. Sorting these halves
  3. Merging the halves
Step 2 is in fact not needed if the list has only one node. One node is sorted. Hence the merge sort algorithm is

  1. If the list has more than one node
  2. Splitting the list into two halves of equal length
  3. Sorting these halves recursively using steps 2 to 4
  4. Merging the halves 

 Split the list into halves

We have seen in this post how to find the mid point of a linked list. Let us use this approach.

We need to use two pointers say slow and fast. Slow moves one node at a time. And fast moves two nodes at a time. When fast has reached end of the list, slow has reached mid point. 

And also we should detach first half of the list from second half.

NODEPTR split_list(NODEPTR head)
{
    NODEPTR slow,fast;
    slow =head; 
    fast = head;
    if(head==NULL || head->next==NULL)     
       return head; /* if only one node is present, return*/
    NODEPTR temp;
    while(fast!=NULL)         
    {       
        fast = fast->next;        
        if(fast!=NULL){
           temp = slow;
           fast = fast->next;
           slow = slow->next;
        }           
     }     
     temp->next  = NULL;/*detach first half of list from second half*/
     return slow; /*this is the head of second half of list*/
}

 Merge sorted sublists

To merge the two sublists which are already sorted we need to compare nodes from two lists, insert the smaller one into the merged list and move to next node in that list. This process has to be repeated until all nodes of both lists are merged. If the two sublists are of unequal length then one list will have nodes remaining, which should be added to merged list

NODEPTR merge_sorted_lists(NODEPTR head1,NODEPTR head2)
{
 NODEPTR newlist = NULL;
 while(head1!=NULL && head2!=NULL )
 {
    if(head1->val <head2->val)
  {
  NODEPTR temp = head1;
  head1 = head1->next; 
  temp->next = NULL;
  newlist = append_node(newlist,temp);
  }
    else
  {
  NODEPTR temp = head2;
  head2 = head2->next; 
  temp->next = NULL;
  newlist = append_node(newlist,temp);
  }
 }
 while(head1!=NULL)
 {
  NODEPTR temp = head1;
  head1 = head1->next; 
  temp->next = NULL;
  newlist = append_node(newlist,temp);
  }
 while(head2!=NULL)
 {
  NODEPTR temp = head2;
  head2 = head2->next; 
  temp->next = NULL;
  newlist = append_node(newlist,temp);
 }
 return newlist;  
}
 

Merge sort the list

 Let us use these two functions in the algorithm given earlier to merge sort the list.

NODEPTR merge_sort(NODEPTR head)
{
     if(head==NULL || head->next==NULL)
       return head; /* list has one node or is empty*/
     NODEPTR mid = split_list(head);
     head = merge_sort(head);/* sort first sublist*/
     mid = merge_sort(mid);/* sort second sublist*/
     head = merge_sorted_lists(head,mid);/* merge these*/
     return head;
}

You can download the entire program from here 
Labels:

Comments

Post a Comment

Popular posts from this blog

In order traversal of nodes in the range x to y

Question : Write a function for in-order traversal of nodes in the range x to y from a binary search tree. This is quite a simple function. As a first solution we can just traverse our binary search tree in inorder and display only the nodes which are in the range x to y. But if the current node has a value less than x, do we have to traverse its left subtree? No. Because all the nodes in left subtree will be smaller than x. Similarly if the current node has a key value more than y, we need not visit its right subtree. Now we are ready to write our algorithm.     if nd is NOT NULL  if nd->val >=x then visit all the nodes of left subtree of nd recursively display nd->val if nd->val <y then visit all the nodes of right subtree of nd recursively  That's all. We have our function ready. void in_order_middle (NODEPTR nd, int x, int y) { if (nd) { if (nd -> val >= x) in_order_middle(nd...
Post a Comment
Read more

Josephus problem

Question: Write a function to delete every k th node from circular linked list until only one node is left. This has a story associated with it. Flavius Josephus was Jewish Historian from 1st century. He and 40 other soldiers were trapped in a cave by Romans. They decided to kill themselves rather than surrendering to Romans. Their method was like this. All the soldiers will stand in a circle and every k th soldier will be shot dead. Josephus said to have calculated the starting point so that he would remain alive. So we have similar problem at hand. We delete every kth node in a circular list. Eventually only one node will be left. e.g. Let us say this is our list And we are deleting every third node.  We will delete 30. Then we delete 60. Next we delete 10. Next it will be 50. Next to be deleted is 20. Next 80. This continues. Implementation   We can count k-1 nodes and delete next node. This can be repeated in  a loop. What must be the termina...
Post a Comment
Read more

Lowest common ancestor of binary search tree

Question : Write a function to print the lowest common ancestor of two nodes in a binary search tree.  Lowest common ancestor of two nodes x and y in a binary tree is the lowest node that has both x and y as descendants. Here lowest common ancestor of 1 and 7 is 3. LCA of 13 and 7 is root - 8. And LCA of 6 and 7 is 6 itself. The program to find gets complicated for an ordinary binary tree. But for a binary search tree, it is quite simple. As we see from the diagram above, the paths to 1 and 4 are common till the node 3. And at 3 they branch in different directions. So 3 is our LCA. That is lowest common ancestor is the node where the paths to x and y from root deviate. As long as they branch in same direction, we continue to traverse. When they branch in different directions, that is the lowest common ancestor. So let us write a simple algorithm, set temp=root if temp->val >x and temp->val>y temp = temp->left else if temp->val<x and ...
Post a Comment
Read more