# 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){

while(fast){
fast = fast->next;
if(fast){
fast = fast->next;
slow = slow->next;
}
}
*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){

while(fast){
fast = fast->next;
if(fast){
fast = fast->next;
slow = slow->next;
}
}
*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;
}

Node * front, *back;
return;

mergeSort(&front);
mergeSort(&back);

}

Node * new_node  = (Node *)malloc(sizeof(Node));
new_node->data = data;
}

while(current){
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL");
}
int main(void) {
Node *front, *back;

printf("\n");

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)