C++ Program to implement Merge Sort using divide and conquer Algorithm

By | 01.03.2017

C++ Program to implement Merge Sort


Write a C++ Program to implement Merge Sort using Divide and Conquer Algorithm. Here’s a Simple Program to implement Merge Sorting using Divide and Conquer Algorithm in C++ Programming Language.


Merge sort is a sorting algorithm for sorting elements of array in either ascending or descending order. Conceptually, a merge sort works as follows:

a) Divide the unsorted list into n sub lists, each containing 1 element(a list of 1 element is considered sorted).

b) Repeatedly merge sub lists to produce new sorted sub lists until there is only 1 sub list remaining. This will be the sorted list.


Here is the source code of the C++ Program to implement Merge Sort using Divide and Conquer Algorithm. This C++ program is successfully compiled and run on Codeblocks. The program output is also shown below.


SOURCE CODE : :


/*  C++ Program to implement Merge Sorting using Divide and Conquer Algorithm  */

#include <iostream>
using namespace std;

int a[100];
void merge(int,int,int);
void merge_sort(int low,int high)
{
 int mid;
 if(low<high)
 {
  mid=(low+high)/2;
  merge_sort(low,mid);
  merge_sort(mid+1,high);
  merge(low,mid,high);
 }
}
void merge(int low,int mid,int high)
{
 int h,i,j,b[100],k;
 h=low;
 i=low;
 j=mid+1;

 while((h<=mid)&&(j<=high))
 {
  if(a[h]<=a[j])
  {
   b[i]=a[h];
   h++;
  }
  else
  {
   b[i]=a[j];
   j++;
  }
  i++;
 }
 if(h>mid)
 {
  for(k=j;k<=high;k++)
  {
   b[i]=a[k];
   i++;
  }
 }
 else
 {
  for(k=h;k<=mid;k++)
  {
   b[i]=a[k];
   i++;
  }
 }
 for(k=low;k<=high;k++) a[k]=b[k];
}
int main()
{
 int num,i;

 cout<<"Enter no.of elements you want to sort:";
 cin>>num;

 cout<<"Enter "<< num <<" Elements : "<<endl;

 for(i=1;i<=num;i++)
 {
  cout<<i<<" Element : ";
  cin>>a[i] ;
 }
 merge_sort(1,num);
 cout<<endl;
 cout<<"After Merge Sort, Sorted Array is :"<<endl;

 for(i=1;i<=num;i++)
 {
      cout<<a[i]<<" ";
 }

 cout<<endl;

return 0;
}

OUTPUT : :


/*  C++ Program to implement Merge Sort using Divide and Conquer Algorithm  */

Enter no.of elements you want to sort: 6

Enter 6 Elements :
1 Element : 5
2 Element : 2
3 Element : 7
4 Element : 1
5 Element : 0
6 Element : 9

After Merge Sort, Sorted Array is :
0       1       2       5       7       9

If you found any error or any queries related to the above program or any questions or reviews , you wanna to ask from us ,you may Contact Us through our contact Page or you can also comment below in the comment section.We will try our best to reach upto you in the short interval.


Thanks for reading the post.

0 0 votes
Article Rating
Subscribe
Notify of
guest
1 Comment
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
H&M

These programs are wonderful! But, the most important thing is missing is the comments! I am not saying that there should be comment for every line of code but where ever it need so. I am sure it is not useful for students or anyone new to programming! That’s why this site has less viewers.
Still, it is something that can be revised anytime.