Merge Sort In C++

What we are going to see through this article is we will see in detail Merge Sort In C++. Merging deployment is the means by which divisions succeed. It is based on the idea of ​​dividing an unsorted row into several sub-rows and merging that sub-row into a sorted row until each sub-row contains an element.

Deployment in programming refers to the placement of elements of a data structure in a specific and meaningful manner. Sorting is an important part of data processing. Efficient sorting algorithms are very important so we can perform the operations that require sorted input.

Merge Sort In C++

Merge Sort in C++

In the merge sequence, a given sequence is sorted and sorted using the winning algorithm. This algorithm divides the input line into sub-rows (until there is only one element in each sub-row) and then re-sorts the sub-rows.

#include <iostream>
 
using namespace std;
 
// A function to merge the two half into a sorted data.
void Merge(int *a, int low, int high, int mid)
{
	// We have low to mid and mid+1 to high already sorted.
	int i, j, k, temp[high-low+1];
	i = low;
	k = 0;
	j = mid + 1;
 
	// Merge the two parts into temp[].
	while (i <= mid && j <= high)
	{
		if (a[i] < a[j])
		{
			temp[k] = a[i];
			k++;
			i++;
		}
		else
		{
			temp[k] = a[j];
			k++;
			j++;
		}
	}
 
	// Insert all the remaining values from i to mid into temp[].
	while (i <= mid)
	{
		temp[k] = a[i];
		k++;
		i++;
	}
 
	// Insert all the remaining values from j to high into temp[].
	while (j <= high)
	{
		temp[k] = a[j];
		k++;
		j++;
	}
 
 
	// Assign sorted data stored in temp[] to a[].
	for (i = low; i <= high; i++)
	{
		a[i] = temp[i-low];
	}
}
 
// A function to split array into two parts.
void MergeSort(int *a, int low, int high)
{
	int mid;
	if (low < high)
	{
		mid=(low+high)/2;
		// Split the data into two half.
		MergeSort(a, low, mid);
		MergeSort(a, mid+1, high);
 
		// Merge them to get sorted output.
		Merge(a, low, high, mid);
	}
}
 
int main()
{
	int n, i;
	cout<<"\nEnter the number of data element to be sorted: ";
	cin>>n;
 
	int arr[n];
	for(i = 0; i < n; i++)
	{
		cout<<"Enter element "<<i+1<<": ";
		cin>>arr[i];
	}
 
	MergeSort(arr, 0, n-1);
 
	// Printing the sorted data.
	cout<<"\nSorted Data ";
	for (i = 0; i < n; i++)
        cout<<"->"<<arr[i];
 
	return 0;
}

Read Also: Find The Largest Among Three Numbers In C++

Output

Case 1:
 
Enter the number of data element to be sorted: 10
Enter element 1: 23
Enter element 2: 987
Enter element 3: 45
Enter element 4: 65
Enter element 5: 32
Enter element 6: 9
Enter element 7: 475
Enter element 8: 1
Enter element 9: 17
Enter element 10: 3
 
Sorted Data ->1->3->9->17->23->32->45->65->475->987

Final Words

What we learned through this article is to Merge Sort In C++. Also if you have any doubts please leave a comment via the comment box. And we ask that you benefit everyone who shared this article with your friends.

Leave a Comment