C++ Program to Implement Merge Sort

«
»

This is a C++ program to sort the given data using Merge Sort.

Problem Description

1. Merge-sort is based on an algorithmic design pattern called divide-and-conquer.
2. It forms tree structure.
3. The height of the tree will be log(n).
4. we merge n element at every level of the tree.
5. The time complexity of this algorithm is O(n*log(n)).

Problem Solution

1. Split the data into two equal half until we get at most one element in both half.
2. Merge Both into one making sure the resulting sequence is sorted.
3. Recursively split them and merge on the basis of constraint given in step 1.
4. Display the result.
5. Exit.

advertisement
Program/Source Code

C++ program to implement Merge sort.
This program is successfully run on Dev-C++ using TDM-GCC 4.9.2 MinGW compiler on a Windows system.

#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;
}
Program Explanation

1. Take input of data.
2. Call MergeSort() function.
3. Recursively split the array into two equal parts.
4. Split them until we get at most one element in both half.
5. Combine the result by invoking Merge().
6. It combines the individually sorted data from low to mid and mid+1 to high.
7. Return to main and display the result.
8. Exit.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
Runtime Test Cases
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

Sanfoundry Global Education & Learning Series – C++ Algorithms.
To practice all C++ Algorithms, here is complete set of 1000 C++ Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.