Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

merge sort

# How to sort a linked list using merge sort

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
{
node* ptr1;
node* ptr2;

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

// Splitting list

// 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;
}

// 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