Get this book -> Problems on Array: For Interviews and Competitive Programming

Algorithm

Complexity

Implementations

Questions

**Merge sort** is a fast comparison based sorting algorithm which can be utilized in sorting a Linked List as well. Merge Sort is preferred for sorting a linked list. The slow random-access performance of a linked list makes some other algorithms such as Quick Sort perform poorly, and others such as Heap Sort completely impossible.

### Algorithm

The algorithm is same as that of Merge Sort will implementation changes to accomodate the structure of Linked List.

### Pseudocode

```
Merge_Sort(head_reference)
```**STEP 1**: If head is NULL or there is only one element in the Linked List
then return the Linked List
**STEP 2**: Divide the linked list into two equal halves.
Split_Linked_List(head, &first_half, &second_half);
**STEP 3**: Sort the two halves first_half and second_half.
MergeSort(first_half);
MergeSort(second_half);
**STEP 4**: Merge the sorted first_half and second_half (using Merge_Sort() recursively)
and update the head pointer using head_reference.
*head_reference = Merge_Sort(first_half, second_half);

### Complexity

- Worst case time complexity:
**Î˜(N log N)** - Average case time complexity:
**Î˜(N log N)** - Best case time complexity:
**Î˜(N log N)** - Space complexity:
**Î˜(1)**

### Implementations

Implementation of applying Merge Sort on a Linked List is as follows:

- C
- Java

### C

```
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int data;
struct Node* next;
};
struct Node* SortedMerge(struct Node* a, struct Node* b);
void FrontBackSplit(struct Node* source, struct Node** frontRef, struct Node** backRef);
void MergeSort(struct Node** headRef)
{
struct Node* head = *headRef;
struct Node* a;
struct Node* b;
if ((head == NULL) || (head->next == NULL))
{
return;
}
FrontBackSplit(head, &a, &b);
MergeSort(&a);
MergeSort(&b);
*headRef = SortedMerge(a, b);
}
struct Node* SortedMerge(struct Node* a, struct Node* b)
{
struct Node* result = NULL;
if (a == NULL)
return(b);
else if (b==NULL)
return(a);
if (a->data <= b->data)
{
result = a;
result->next = SortedMerge(a->next, b);
}
else
{
result = b;
result->next = SortedMerge(a, b->next);
}
return(result);
}
void FrontBackSplit(struct Node* source, struct Node** frontRef, struct Node** backRef)
{
struct Node* fast;
struct Node* slow;
slow = source;
fast = source->next;
while (fast != NULL)
{
fast = fast->next;
if (fast != NULL)
{
slow = slow->next;
fast = fast->next;
}
}
* frontRef = source;
* backRef = slow->next;
slow->next = NULL;
}
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
int main()
{
struct Node* res = NULL;
struct Node* a = NULL;
push(&a, 3);
push(&a, 1);
push(&a, 2);
MergeSort(&a);
getchar();
return 0;
}
```

### Java

`public class linkedList { node head = null; static class node { int val; node next;`

`public node(int val) { this.val = val; } } node sortedMerge(node a, node b) { node result = null; if (a == null) return b; if (b == null) return a; if (a.val <= b.val) { result = a; result.next = sortedMerge(a.next, b); } else { result = b; result.next = sortedMerge(a, b.next); } return result; } node mergeSort(node h) { if (h == null || h.next == null) { return h; } node middle = getMiddle(h); node nextofmiddle = middle.next; middle.next = null; node left = mergeSort(h); node right = mergeSort(nextofmiddle); node sortedlist = sortedMerge(left, right); return sortedlist; } node getMiddle(node h) { //Base case if (h == null) return h; node fastptr = h.next; node slowptr = h; while (fastptr != null) { fastptr = fastptr.next; if(fastptr!=null) { slowptr = slowptr.next; fastptr=fastptr.next; } } return slowptr; } void push(int new_data) { node new_node = new node(new_data); new_node.next = head; head = new_node; } public static void main(String[] args) { linkedList li = new linkedList(); li.push(3); li.push(2); li.push(1); li.head = li.mergeSort(li.head); }`

`}`

### Questions

#### What is the time complexity of this algorithm if Linked List is already sorted?

O(N)

O(1)

O(N log N)

O(log N)