×

Search anything:

# Merge Sort a singly Linked List Get this book -> Problems on Array: For Interviews and Competitive Programming

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

``````

STEP 1: If head is NULL or there is only one element in the Linked List

STEP 2: Divide the linked list into two equal halves.

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)
``````

### 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);
{
struct Node* a;
struct Node* b;
{
return;
}
MergeSort(&a);
MergeSort(&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;
}
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

``````
{
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 &lt;= 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);
}

public static void main(String[] args)
{

li.push(3);
li.push(2);
li.push(1);

}

``````}
``````

### 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) #### OpenGenus Tech Review Team

The official account of OpenGenus's Technical Review Team. This team review all technical articles and incorporates peer feedback. The team consist of experts in the leading domains of Computing.