# Merge Sort for Linked Lists

## Merge sort is the most preferred sorting algorithm for linked lists as it avoids the need of auxiliary space and has the time complexity of just O(nlogn).

Given a linked list, write a function that will sort the linked list by doing merge sort.

### Example

INPUT :
4->1->5->2->3

OUTPUT :
1->2->3->4->5

Time Complexity : O(nlogn)

## Algorithm

mergeSort()

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  ie, splitLL() splits list into list1 and list2

3. Sort the two halves     ie, recursively call mergeSort(list1), mergeSort(list2)

4. Merge the two sorted halves ie, mergeSortedList(list1,list2) does this job

## C++ Program

``````#include <bits/stdc++.h>
using namespace std;

struct LLNode{
int data;
LLNode *next;
};
//Prototypes
LLNode* mergeSortedLists(LLNode* list1, LLNode* list2);
void splitLL(LLNode* head, LLNode** list1, LLNode** list2);

//Main function, which will sort the lists
{
LLNode* list1;
LLNode* list2;
/* Base case -- length 0 or 1 */
{
return;
}

// Split list(head) into 'list1' and 'list2' sublists

/* Recursively sort the sublists */
mergeSort(&list1);
mergeSort(&list2);
//merge the two sorted lists together
}
//Merge the two sorted lists
LLNode* mergeSortedLists(LLNode* list1, LLNode* list2)
{
//display(&list1);
//cout<<(list1->data);
LLNode* result = NULL;

/* Base cases */
if (list1 == NULL)
return(list2);
else if (list2==NULL)
return(list1);

/* Pick either list1 or list2, and recur */
if (list1->data <= list2->data)
{
result = list1;
result->next = mergeSortedLists(list1->next, list2);
}
else
{
result = list2;
result->next = mergeSortedLists(list1, list2->next);
}
return(result);
}

//split the nodes into two halves
LLNode** list1, LLNode** list2)
{
LLNode* fast;
LLNode* slow;
{
/* length < 2 cases */
*list2 = NULL;
}
else
{

// Move 'fast' two nodes, and move 'slow' one node //
while (fast != NULL)
{
fast = fast->next;
if (fast != NULL)
{
slow = slow->next;
fast = fast->next;
}
}

/* 'slow' is before the midpoint in the list, so split it in two
at that point. */
*list2 = slow->next;
slow->next = NULL;
}
}
{
LLNode*curr=new LLNode;
//make a new node with this data and next pointing to NULL
curr->data=dataToBeInserted;
curr->next=NULL;

if(*head==NULL) //if list is empty then set the current formed node as head of list

else //make the next of the current node point to the present head and make the current node as the new head
{
}

//O(1) constant time
}

//Will print the list
{
while(temp!=NULL) //till the list ends (NULL marks ending of list)
{
if(temp->next!=NULL)
cout<<temp->data<<" ->";
else
cout<<temp->data;

temp=temp->next; //move to next node
}
//O(number of nodes)
cout<<endl;
}

int main()
{

LLNode *head = NULL; //initial list has no elements

cout<<"\nCurrent List is :-\n";