### C++ program to Sort a Linked List Using Merge Sort

Program:
#include<iostream>

using namespace std;

// A structure representing a node of a linked list.
struct node
{
int data;
node *next;
};

// A function creating a new node.
node* NewNode(int d)
{
struct node *temp = new node;
temp->data = d;
temp->next = NULL;
// Returning temp as the new node.
return temp;
}

// A function adding the given data at the end of the linked list.
{
struct node *newnode;
newnode = NewNode(data);

if(tail == NULL)
{
tail = newnode;
}
// If tail is not null assign newnode to the next of tail.
else
{
tail->next = newnode;
// Shift tail pointer to the added node.
tail = tail->next;
}

return tail;
}

node* Merge(node* h1, node* h2)
{
node *t1 = new node;
node *t2 = new node;
node *temp = new node;

// Return if the first list is empty.
if(h1 == NULL)
return h2;

// Return if the Second list is empty.
if(h2 == NULL)
return h1;

t1 = h1;

// A loop to traverse the second list, to merge the nodes to h1 in sorted way.
while (h2 != NULL)
{
// Taking head node of second list as t2.
t2 = h2;

// Shifting second list head to the next.
h2 = h2->next;
t2->next = NULL;

// If the data value is lesser than the head of first list add that node at the beginning.
if(h1->data > t2->data)
{
t2->next = h1;
h1 = t2;
t1 = h1;
continue;
}

// Traverse the first list.
flag:
if(t1->next == NULL)
{
t1->next = t2;
t1 = t1->next;
}
// Traverse first list until t2->data more than node's data.
else if((t1->next)->data <= t2->data)
{
t1 = t1->next;
goto flag;
}
else
{
// Insert the node as t2->data is lesser than the next node.
temp = t1->next;
t1->next = t2;
t2->next = temp;
}
}

// Return the head of new sorted list.
return h1;
}

// A function implementing Merge Sort on linked list using reference.
{
node *first = new node;
node *second = new node;
node *temp = new node;

// Return if list have less than two nodes.
if(first == NULL || first->next == NULL)
{
return;
}
else
{
// Break the list into two half as first and second as head of list.
while(first->next != NULL)
{
first = first->next;
if(first->next != NULL)
{
temp = temp->next;
first = first->next;
}
}
second = temp->next;
temp->next = NULL;
}

// Implementing divide and conquer approach.
MergeSort(&first);
MergeSort(&second);

// Merge the two part of the list into a sorted one.
}

int main()
{
int n, i, num;
struct node *head = new node;
struct node *tail = new node;
tail = NULL;
cout<<"\nEnter the number of data element to be sorted: ";
cin>>n;

for(i = 0; i < n; i++)
{
cout<<"Enter element "<<i+1<<": ";
cin>>num;

}

// Send reference of head into MergeSort().

// Printing the sorted data.
cout<<"\nSorted Data ";

{
}
return 0;
}
Output:
Enter the number of data element to be sorted: 10
Enter element 1: 3
Enter element 2: 8
Enter element 3: 9
Enter element 4: 4
Enter element 5: 5
Enter element 6: 7
Enter element 7: 6
Enter element 8: 2
Enter element 9: 0
Enter element 10: 1

Sorted Data ->0->1->2->3->4->5->6->7->8->9

#### More Articles of Shaik Aftab Ahmed:

Name Views Likes
C++ Program to Find the Frequency of Odd & Even Numbers in the given Matrix 434 1
C++ program to Sort a Linked List Using Merge Sort 390 1
C++ Program to Implement a Linked List representation of a Binary tree 412 1
C++ Program to Check for balanced parentheses in an expression 268 1
C++ Program to Perform Inorder, Preorder, Postorder traversals in a binary tree. 319 1
C++ program to print Indian flag 432 1
C++ program to Convert a multi level linked list to a singly linked list 312 1
C++ program to print right view of a Binary tree using queue 263 1
C++ Program to implement Huffman Coding Compression Algorithm 2037 1
C++ Program to Create a Height Balanced Binary Tree 300 1
C++ program to implement Prims algorithm 1006 1
C++ Program for BFS Traversal 324 1
C++ Progam to Evaluate a Prefix Expression 568 1
C++ Program to Implement Queue using Linked List 291 1
C++ implementation of Stack using Linked list 356 1
C++ program to find the intersection point of two linked lists 385 1
C++ program to count the inversions in the given array 292 1
C++ program to perform D.N.F sort 342 1
C++ program to print all possible subsets of a String 306 1
C++ program to count the number of ones in a binary representation of a number 333 1
C++ program to print all possible subsets of a set 336 1
C++ program to find the largest word in a String 302 1
C++ Program to print a matrix in Spiral order 408 1
C++ program to convert from Binary to Decimal, Octal to Decimal, Hexadecimal to Decimal 332 1
C limits library 369 1
Program to add two Binary numbers 360 1