//here Im posing different ways of Merge sort programs, you can follow whichever you want
Merge Sort
Merge Sort
What is Merge Sort algorithm? How to implement Merge Sort in C++?
Merge Sort is a divide and conquer algorithm.
In the best/ average/ worst case it gives a time complexity of O(n log n).
Conceptually, a merge sort works as follows:
If the list is of length 0 or 1, then it is already sorted. Otherwise:
Divide the unsorted list into two sublists of about half the size.
Sort each sublist recursively by re-applying the merge sort.
Merge the two sublists back into one sorted list.
Example:
#include <iostream.h>
const int MAX = 5 ;
class array
{
private :
int *a ;
int size ;
int count ;
public :
array( ) ;
array ( int sz ) ;
void add ( int num ) ;
void display( ) ;
void merge_sort(int low,int high);
void merge(int low,int mid,int high);
~array( ) ;
} ;
array :: array( )
{
count = size = 0 ;
a = NULL ;
}
array :: array( int sz )
{
count = 0 ;
size = sz ;
a = new int[sz] ;
}
void array :: add ( int num )
{
if ( count < size )
{
a[count] = num ;
count++ ;
}
else
cout << "\nArray is full" << endl ;
}
void array :: display( )
{
for ( int i = 0 ; i < count ; i++ )
cout << a[i] << "\t" ;
cout << endl ;
}
void array :: 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 array :: merge(int low,int mid,int high)
{
int h,i,j,b[50],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];
}
array :: ~array( )
{
delete a ;
}
void main( )
{
array a ( MAX ) ;
a.add ( 11 ) ;
a.add ( 2 ) ;
a.add ( 9 ) ;
a.add ( 13 ) ;
a.add ( 57 ) ;
cout << "\nMerge sort.\n" ;
a.merge_sort (0,4) ;
cout << "\nArray after sorting: " << endl ;
a.display( ) ;
}
Example 2: without using classes
#include <iostream>using namespace std;void merge(int*,int*,int,int,int);void mergesort(int *a, int*b, int low, int high){ int pivot; if(low<high) { pivot=(low+high)/2; mergesort(a,b,low,pivot); mergesort(a,b,pivot+1,high); merge(a,b,low,pivot,high); }}void merge(int *a, int *b, int low, int pivot, int high){ int h,i,j,k; h=low; i=low; j=pivot+1; while((h<=pivot)&&(j<=high)) { if(a[h]<=a[j]) { b[i]=a[h]; h++; } else { b[i]=a[j]; j++; } i++; } if(h>pivot) { for(k=j; k<=high; k++) { b[i]=a[k]; i++; } } else { for(k=h; k<=pivot; k++) { b[i]=a[k]; i++; } } for(k=low; k<=high; k++) a[k]=b[k];}int main(){ int a[] = {12,10,43,23,-78,45,123,56,98,41,90,24}; int num; num = sizeof(a)/sizeof(int); int b[num]; mergesort(a,b,0,num-1); for(int i=0; i<num; i++) cout<<a[i]<<" "; cout<<endl;}
