**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/2^{th} 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.

Pingback: Intersection of two sort linked lists – Algorithms and Me()

Pingback: Union of two linked lists implementation - Algorithms and Me()

Pingback: Middle node of linked list : Hare and Tortoise algorithm - Algorithms and Me()