Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

merge sort
linkedlist

How to sort a linked list using merge sort

Educative Answers Team

Merge sort is one of the most famous divide-and-conquer sorting algorithms. This algorithm can be used to sort values in any traversable data structure (i.e., a linked list).

Algorithm for merge sort

  1. If: The list contains one or fewer elements, return the same list.
  2. Else: Divide the list into halves using the splitting function.
  3. Sort: Sort ​the two halves of the list.
  4. At the end, merge the sorted lists.

The illustration below shows this algorithm:

1 of 6

Implementation

In the code below, we have used two helper functions: the SplitList() function is used to divide the list into two halves, ​and the MergeSortedList() function merges the two sorted lists, recursively.

// C++ code for linked list merged sort 
#include <bits/stdc++.h> 
using namespace std; 

// Link list node 
class node { 
public: 
	int data; 
	node* next; 
}; 

// Merging two sorted lists.
node* MergeSortedList(node* lst1, node* lst2) 
{ 
	node* result = NULL; 

	// Base Cases
	if (lst1 == NULL) 
		return (lst2); 
	else if (lst2 == NULL) 
		return (lst1); 

	// recursively merging two lists
	if (lst1->data <= lst2->data) { 
		result = lst1; 
		result->next = MergeSortedList(lst1->next, lst2); 
	} 
	else { 
		result = lst2; 
		result->next = MergeSortedList(lst1, lst2->next); 
	} 
	return result; 
} 

// Splitting two into halves.
// If the size of the list is odd, then extra element goes in the first list.
void SplitList(node* source, node** front, node** back) 
{ 
	node* ptr1; 
	node* ptr2; 
	ptr2 = source; 
	ptr1 = source->next; 

	// ptr1 is incrmented twice and ptr2 is icremented once.
	while (ptr1 != NULL) { 
		ptr1 = ptr1->next; 
		if (ptr1 != NULL) { 
			ptr2 = ptr2->next; 
			ptr1 = ptr1->next; 
		} 
	} 

	// ptr2 is at the midpoint.
	*front = source; 
	*back = ptr2->next; 
	ptr2->next = NULL; 
} 


// Merge Sort
void MergeSort(node** thead) 
{ 
	node* head = *thead; 
	node* ptr1; 
	node* ptr2; 

  // Base Case
	if ((head == NULL) || (head->next == NULL)) { 
		return; 
	} 

	// Splitting list
	SplitList(head, &ptr1, &ptr2); 

	// Recursively sorting two lists.
	MergeSort(&ptr1); 
	MergeSort(&ptr2); 

	// Sorted List.
	*thead = MergeSortedList(ptr1, ptr2); 
} 



// Printing List.
void printList(node* tnode) 
{ 
	while (tnode != NULL) { 
		cout << tnode->data << " "; 
		tnode = tnode->next; 
	} 
} 

// Push function for inserting nodes in the list.
void push(node** thead, int new_data) 
{ 
	node* new_node = new node(); 
	new_node->data = new_data; 
	new_node->next = (*thead); 
	(*thead) = new_node; 
} 

// Driver Program.
int main() 
{ 
  // Empty list
	node* res = NULL; 
	node* MyList = NULL; 

  // List: 10->4->15->1->2->12->54
	push(&MyList, 54); 
	push(&MyList, 12); 
	push(&MyList, 2); 
	push(&MyList, 1); 
	push(&MyList, 15); 
	push(&MyList, 4);
    push(&MyList, 10); 

	cout << "Unsorted Linked List: "; 
	printList(MyList); 
	cout << "\n"; 

	MergeSort(&MyList); 

	cout << "Sorted Linked List: "; 
	printList(MyList); 

	return 0; 
} 

RELATED TAGS

merge sort
linkedlist
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring