Merge Sort is a divide and conquer approac for sorting and a comparitively faster way of comparison based sorting which is sometimes preferred for sorting a linked list. Due to the slow speed of random accessing of any element in the linked list, some algorithms like quick sort perform poorly and others like heapsort can never sort a linked list effectively.
Steps for Algorithm:
The Merge Sort strategy is for sorting data elements of a linked list would be:
-
Split the list into equal part sublists.
-
Sort the sublists recursively and then merge the sorted lists together to form the answer.
Let the head be the first node of the linked list which is to be sorted and head_reference be the pointer to head.
MergeSort(head_reference)
STEP 1: If head is NULL or there is only one element in the linked list, then return the linked list, because it is already sorted.
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, recursively and update the head pointer using head_reference.
Pseudocode:
void MergeSort(struct node** headRef)
{
struct node* head = *headRef;
struct node* a; struct node* b; // Base case -- length 0 or 1
if ((head == NULL) || (head->next == NULL)) {
return;
}
FrontBackSplit(head, &a, &b); // Split head into 'a' and 'b' sublists
MergeSort(&a); // Recursively sort the sublists
MergeSort(&b);
*headRef = SortedMerge(a, b); // answer = merge the two sorted lists together
}
Now let's head to the final implementation of the code in C/C++ language.
Implementation in C/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;
}
Here, firstly we will divide the linked list into two equal halves, after that we will sort the two halves using MergeSort() function. Finally, we will merge the two sorted halves of the linked list using the SortedMerge() function. This happens recursively, so in a way we break the linked list into two sublists, then those two sublists are further broken into four sublists and so on until we set a sublist with a single element which is alredy sorted, then we start merging the sublists.
Time Complexity of the Algorithm
The time complexity of this algorithm is O(nlogn)
NOTE: If the linked list is already sorted, then time complexity will be O(n).
You may also like:
