Given an unsorted linked list, sort the list using merge sort.

Example:

3 -> 4 -> 5-> 1 -> 2

Output:

1 -> 2 -> 3 -> 4 -> 5

Merge sort is a divide and conquer algorithm.
Here we divide the elements into smaller parts, then while merging them, we merge according to sorted order.

Example:

Consider below elements, we start dividing exactly half of the array.

Input: 3, 4, 1, 2, 9, 7, 8, 5

Divide: 3, 4, 1, 2, 9, 7, 8, 5

Divide: 3, 4, 1, 2, 9, 7, 8, 5

Merge: 3, 4, 1, 2 7, 9 5, 8

Merge: 1, 2, 3, 4, 5, 7, 8, 9

Merge: 1, 2, 3, 4, 5, 7, 8, 9

In similar way, we divide the given linked list and then merge them to get the desired result.
To achieve, we need to make use of recursion algorithm.

Solution in C++

#include<iostream>
#include<vector>
#include<string>

using namespace std;

struct Node
{
	int data;
	Node *next;

	Node(int x)
	{
		data = x;
		next = NULL;
	}
};


void print_list(Node *head)
{
	Node *start = head;

	while(start)
	{
		cout<<start->data<<" -> ";
		start = start->next;
	}
	cout<<"\n";
}

Node* merge_nodes(Node* l1, Node* l2)
{
	Node helper_node(0);
	Node* cur = &helper_node;


	// add elements at their respective postion 
	while (l1 != NULL && l2 != NULL)
	{
		if (l1->data < l2->data)
		{
			cur->next = l1;
			l1 = l1->next;
		}
		else
		{
			cur->next = l2;
			l2 = l2->next;
		}

		cur = cur->next;
	}

	// if any one of the list is empty and other list has elements in it,
	// add them appropriately 
	if (l1 != NULL)
		cur->next = l1;
	else
		cur->next = l2;

	return helper_node.next;
}


Node* sort_list(Node* head) 
{
	if (head == NULL || head->next == NULL)
		return head;

	Node* slow = head;
	Node* fast = head->next;

// get the middle of the list
	while (fast != NULL && fast->next != NULL)
	{
		slow = slow->next;
		fast = fast->next->next;
	}

//"fast" will hold the start of 2nd half
	fast = slow->next;
	slow->next = NULL;

// call recursively "sort_list", when all the nodes are divided,
// call "merge_nodes" functions to merge all the divided nodes.
	return merge_nodes(sort_list(head), sort_list(fast));
}



int main()
{
	Node *head = new Node(2);
	head -> next = new Node(1);
	head -> next -> next = new Node(4);
	head -> next -> next -> next = new Node(3);
	head -> next -> next -> next  -> next = new Node(6);
	head -> next -> next -> next  -> next -> next = new Node(5);
	head -> next -> next -> next  -> next -> next -> next = new Node(8);

	cout<<"The original list = "<<endl;
	print_list(head);

	cout<<"Sorting the list ... "<<endl;;
	Node *new_head = sort_list(head);

	cout<<"\nAfter sorting: "<<endl;

	print_list(new_head);


	return 0;
}

Output:

The original list =
2 -> 1 -> 4 -> 3 -> 6 -> 5 -> 8 ->
Sorting the list …

After sorting:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 8 ->