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;	
};
void display(LLNode**head);
//Prototypes
LLNode* mergeSortedLists(LLNode* list1, LLNode* list2);
void splitLL(LLNode* head, LLNode** list1, LLNode** list2);

//Main function, which will sort the lists
void mergeSort(LLNode** head)
{
  	LLNode* list1;
  	LLNode* list2;
  	/* Base case -- length 0 or 1 */
  	if ((*head == NULL) || ((*head)->next == NULL))
  	{
    	return;
  	}
 
  	// Split list(head) into 'list1' and 'list2' sublists 
  	splitLL(*head, &list1, &list2); 
 
  	/* Recursively sort the sublists */
  	mergeSort(&list1);
  	mergeSort(&list2);
  	//merge the two sorted lists together
  	*head = mergeSortedLists(list1, list2);
}
//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 
void splitLL(LLNode* head,
          LLNode** list1, LLNode** list2)
{
  LLNode* fast;
  LLNode* slow;
  if (head==NULL || head->next==NULL)
  {
    /* length < 2 cases */
    *list1 = head;
    *list2 = NULL;
  }
  else
  {
    slow = head;
    fast = head->next;
 
    // 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. */
    *list1 = head;
    *list2 = slow->next;
    slow->next = NULL;
  }
}
void insertAtBeginning(LLNode**head,int dataToBeInserted)
{
	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
			*head=curr;
		
	else //make the next of the current node point to the present head and make the current node as the new head
		{
			curr->next=*head;
			*head=curr;
		}
		
		//O(1) constant time
}

//Will print the list
void display(LLNode**head)
{
	LLNode*temp=*head;
	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
	insertAtBeginning(&head,6);
	insertAtBeginning(&head,16);
	insertAtBeginning(&head,15);
	insertAtBeginning(&head,50);
	insertAtBeginning(&head,1);
	insertAtBeginning(&head,23);

	
	cout<<"\nCurrent List is :-\n";
	display(&head);
	mergeSort(&head);
	cout<<"After doing Merge Sort"<<endl;
	display(&head);
	return 0;
}
Try It

 


Next > < Prev
Scroll to Top