Merge sort on linked list implementation

Merge sort on linked list

We have seen merge sort implementation on array. Today, let’s discuss how the same algorithm can be implemented merge sort on linked list
Steps are again the same as merge sort in an array.

1. Split the input space in two parts.
2. Sorted individual parts
3. Merge smaller part into bigger one.

Difference between implementation with arrays and linked list is that in array based implementation, middle element is easily available with (start + end)/2. However, to find middle element is not available in linked list in O(1) operations. Hence, first question : how to split linked list into two  halves to divide it into two smaller list and then sort them. In other words, we need to find n/2th node. To do so, there is Hare and Tortoise algorithm to find middle node of linked list.  In Hare and Tortoise algorithm uses two pointers; one called as fast (referring to Hare ) and other as slow, (referring to Tortoise).  Fast pointer moves twice as fast as slow pointer. So, when fast pointer reaches end of linked list, slow is exactly at the middle node. Split function is implemented as below.

void split(Node *head, Node **front, Node **back){
  Node * fast = head->next;
  Node * slow = head;
	
  while(fast){
   fast = fast->next;
   if(fast){
    fast = fast->next;
    slow = slow->next;
   }
  }
  *front = head; 
  *back = slow->next;
  slow->next = NULL;
}

Once split of linked list is done, next step is to recurse till there is only one node remaining. This will be the base case for recursion. Last action is to merge two sorted sub linked lists to bigger list. You can read in detail how to merge two sorted linked lists in single linked list.

Merge sort on linked list : Algorithm

1) If head is NULL or there is only one element in the Linked List 
    then return.
2) Else divide the linked list into two halves.  
      Split(head, &front, &back); /* front and back are two halves of  linked list */
3) Sort the two halves with front and back as head pointers
      MergeSort(front);
      MergeSort(back);
4) Merge the sorted front and back and update the head pointer using headRef.

Merge sort on linked list : implementation

#include <stdio.h>
#include <stdlib.h>

typedef struct node{
  int data;
  struct node *next;
}Node;

void split(Node *head, Node **front, Node **back){
	
  Node *fast = head->next;
  Node *slow = head;
	
  while(fast){
	fast = fast->next;
	if(fast){
	  fast = fast->next;
	  slow = slow->next;
	}
  }
  *front = head; 
  *back = slow->next;
  slow->next = NULL;
}

Node * merge(Node *a, Node *b){
 Node *result = NULL;
 if(a ==  NULL)
   return b;
 else if(b == NULL)
    return a;
 
 /* For the first node, we would set the result to either a or b */
  if(a->data <= b->data){
    result = a;
    /* Result's next will point to smaller one in lists 
    starting at a->next  and b */
    result->next = merge(a->next,b);
   }
   else {
    result = b;
    /*Result's next will point to smaller one in lists 
    starting at a and b->next */
    result->next = merge(a,b->next);
   }
   return result;
}

void mergeSort(Node **headRef){
  Node * front, *back;
  Node * head  = *headRef;
  if(head == NULL || head->next == NULL)
	return;
	
  split(head, &front, &back);
  mergeSort(&front);
  mergeSort(&back);

  *headRef = merge(front, back);
}

void push(Node **headRef, int data){
  Node * new_node  = (Node *)malloc(sizeof(Node));
  new_node->data = data;
  new_node->next = *headRef;
  *headRef  = new_node;
}

void printList(Node * head){
  Node * current = head;
  while(current){
	printf("%d -> ", current->data);
	current = current->next;
  }
  printf("NULL");
}
int main(void) {
	// your code goes here
  Node *head = NULL;
  Node *front, *back;
  push(&head,5);
  push(&head,8);
  push(&head,7);
  push(&head,3);
  push(&head,1);

  mergeSort(&head);
  printf("\n");
  printList(head);

  return 0;
}

Let’s take an example and see how code work for merge sort on linked lists. Given linked list is as follows, execution is shown in detail

Original list:1 -> 3 -> 7 -> 8 -> 5 -> NULL
Split parts :
1 -> 3 -> 7 -> NULL
8 -> 5 -> NULL

Split(1)
Original list:1 -> 3 -> 7 -> NULL
Split parts :
1 -> 3 -> NULL
7 -> NULL  (4)

Split(2)
Original list:1 -> 3 -> NULL
Split parts :
1 -> NULL (1)
3 -> NULL (2)

Since only one element remaining, merging starts
After Merging (1) and (2):
1 -> 3 -> NULL (3)
After Merging (3) and (4)
1 -> 3 -> 7 -> NULL (5)

Now,second part it taken split(8) 
Original list:8 -> 5 -> NULL
Split parts :
8 -> NULL (6)
5 -> NULL (7)
After Merging (6) and (7):
5 -> 8 -> NULL (8)

After Merging (5) and (8)
1 -> 3 -> 5 -> 7 -> 8 -> NULL

Complexity of merge sort implementation on linked list is again O(nlogn)
Please share if something wrong or missing. If you are interested in contributing to site or have an interview experience to share, please contact us and earn money too.