Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Merge sort is usually used to sort linked lists. The slow random access performance of linked lists makes some other algorithms (such as quicksort) perform poorly, while others (such as heap sort) are completely impossible.

Let head be the first node in the list to be sorted, and headRef be the pointer to head. Note that we need to reference head in MergeSort(), because the implementation below changes the next link to sort the list (not the data on the node), so if the data in the original header is not the minimum in the list.

Merge sort (headRef) 1) returns if head is NULL or there is only one element in the list. 2) Otherwise split the list in half. FrontBackSplit(head, &a, &b); /* A and b are halves */ 3) Sort the halves of a and B. Merge sort (1); Merge sort (b); 4) Merge sorted A and B (using SortedMerge() discussed here) and update the header pointer with headRef. *headRef = SortedMerge(a, b);Copy the code
#include <bits/stdc++.h>
using namespace std;

class Node {
public:
	int data;
	Node* next;
};

Node* SortedMerge(Node* a, Node* b);
void FrontBackSplit(Node* source, Node** frontRef, Node** backRef);

void MergeSort(Node** headRef)
{
	Node* head = *headRef;
	Node* a;
	Node* b;

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

	FrontBackSplit(head, &a, &b);

	MergeSort(&a);
	MergeSort(&b);

	*headRef = SortedMerge(a, b);
}

Node* SortedMerge(Node* a, Node* b)
{
	Node* result = NULL;
	if (a == NULL)
		return (b);
	else if (b == NULL)
		return (a);
	if (a->data <= b->data) {
		result = a;
		result->next = SortedMerge(a->next, b);
	}
	else {
		result = b;
		result->next = SortedMerge(a, b->next);
	}
	return (result);
}

void FrontBackSplit(Node* source, Node** frontRef, Node** backRef)
{
	Node* fast;
	Node* slow;
	slow = source;
	fast = source->next;

	while(fast ! =NULL) {
		fast = fast->next;
		if(fast ! =NULL) {
			slow = slow->next;
			fast = fast->next;
		}
	}

	*frontRef = source;
	*backRef = slow->next;
	slow->next = NULL;
}

void printList(Node* node)
{
	while(node ! =NULL) {
		cout << node->data << ""; node = node->next; }}void push(Node** head_ref, int new_data)
{
	Node* new_node = new Node(a); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; }int main(a)
{
	Node* res = NULL;
	Node* a = NULL;
	push(&a, 15);
	push(&a, 10);
	push(&a, 5);
	push(&a, 20);
	push(&a, 3);
	push(&a, 2);

	MergeSort(&a);

	cout << "Sorted Linked List is: \n";
	printList(a);

	return 0;
}
Copy the code

Output:

Sorted Linked List is: 
2 3 5 10 15 20
Copy the code

Time complexity: O(n*log n)\

Space complexity: O(n*log n)

Method 2: This method is simpler and uses log n space.

Merge sort () :

  1. If the list size is 1, the header is returned
  2. Use the tortoise and rabbit method to find the middle
  3. Store mid’s next in Head2, the right sublist.
  4. Now make the next midpoint empty.
  5. Call mergeSort() recursively on the left and right sublists to store the new headers of the left and right sublists.
  6. Merge () is called with the argument given the new head of the left and right sublists and stores the final head returned after the merge.
  7. Returns the final header of the merged list.

Merge (head 1, head 2) :

  1. Take a pointer to say Merge to store the merged list and a virtual node in it.
  2. Take a pointer temp and assign it merge.
  3. If the data of head1 is less than that of head2, head1 is stored in Next of Temp and moved to next of Head1.
  4. Otherwise, store head2 next to Temp and move head2 to next to head2.
  5. Move temp to the next temp.
  6. Repeat steps 3, 4, and 5 until head1 is not null and head2 is not null.
  7. Now add any remaining nodes from the first or second list to the merged list.
  8. Returns the next merge (this ignores the virtuality and returns the head of the final merge list)
#include<iostream>
using namespace std;

struct Node{
	int data;
	Node *next;
};

void insert(int x,Node **head) {
	if(*head == NULL){
		*head = new Node;
		(*head)->data = x;
		(*head)->next = NULL;
		return;
	}
	Node *temp = new Node;
	temp->data = (*head)->data;
	temp->next = (*head)->next;
	(*head)->data=x;
	(*head)->next=temp;
}

void print(Node *head) {
	Node *temp=head;
	while(temp! =NULL) {
		cout<<temp->data<<""; temp = temp->next; }}Node *merge(Node *firstNode,Node *secondNode) {
	Node *merged = new Node;
	Node *temp = new Node;

	merged = temp;

	while(firstNode ! =NULL&& secondNode ! =NULL) {
	
		if(firstNode->data<=secondNode->data) {
			temp->next = firstNode;
			firstNode = firstNode->next;
		}
		
		else {
			temp->next = secondNode;
			secondNode = secondNode->next;
		}
		temp = temp->next;
	}

	while(firstNode! =NULL) {
		temp->next = firstNode;
		firstNode = firstNode->next;
		temp = temp->next;
	}

	while(secondNode! =NULL) {
		temp->next = secondNode;
		secondNode = secondNode->next;
		temp = temp->next;
	}
	return merged->next;
}

Node *middle(Node *head) {
	Node *slow = head;
	Node *fast = head->next;
	
	while(slow->next ! =NULL&& (fast! =NULL&& fast->next! =NULL)) {
		slow = slow->next;
		fast = fast->next->next;
	}
	return slow;
}

Node *sort(Node *head){
	
	if(head->next == NULL) {
		return head;
	}

	Node *mid = new Node;
	Node *head2 = new Node;
	mid = middle(head);
	head2 = mid->next;
	mid->next = NULL;
	Node *finalhead = merge(sort(head),sort(head2));
	return finalhead;
}
int main(void) {
	Node *head = NULL;
	int n[]={7.10.5.20.3.2};
	for(int i=0; i<6; i++) {insert(n[i],&head); 
	}
cout<<"\nSorted Linked List is: \n";
	print(sort(head));	
	return 0;
}
Copy the code

Output:

Sorted Linked List is: 
2 3 5 7 10 20 
Copy the code

Time complexity: O(n*log n)

Space complexity: O(log N)

🥇 past quality articles

Singly linked list data structure of the chain table from the introduction of | first set of singly linked list data structure linked list and array | second singly linked list data structure of chain table insert | | delete nodes of the third set of singly linked list data structure of the fourth set of singly linked list data structure to delete a given location linked list node | the fifth set Singly linked list data structure of the check method of array and list | singly linked list data structure of the set of 6-1 check method of array and list | set 6-2 singly linked list data structure of the length of the chain table lookup (iteration and recursion) | 7 sets of singly linked list data structure of switching nodes in the list without exchanging data | 8 sets Singly linked list data structure of the inversion list | 9 sets of singly linked list data structure of merging two sorted lists | 10 sets

📣 Endnote: For more information on data structures, you can follow me: Haiyong, I hope you found this article helpful.

If you see this, thank you for reading 🙂

💌 welcomes your comments and suggestions in the comments section! 💌

If you really learn something new from this article, like it, bookmark it and share it with your friends. 🤗 and finally, don’t forget ❤ or 📑.