# Data Structure How to implement Merge Sort in C

Data Structure: How to implement Merge Sort in C++?

Merging is the process of combining two or more sorted files into a third sorted file. Merge sort is based on the divide and conquer paradigm. It can be explained as …. Let A[p…..r] is given array with indices p = 1 to r = n. Then steps can be

1. Divide Step: If a given array A has zero or one element, then simply return; it is already sorted. Otherwise split A[p…..r] into two subarrays as A[p….q] and A[q+1…..r] each containing about the half of the elements.
2. Conquer Step: Conquer by recursively sorted the two sub-arrays A[p….q] and A[q+1….r]
3. Combine Step: Combine the elements back in A[p…..r] by merging the two sorted sub-arrays into the sorted sequence. Note that: the recursion bottoms out when the sub-array has just one element. So that it is trivially sorted.

Source Code:

```#include

using namespace std;

class MergeSort{
public:
int no_of_elements;
int elements;
public:
void getarray();
void partition(int [] ,int ,int);
void sortit(int [], int , int, int);
void display();
};

void MergeSort::getarray(){
cout<<"How many elements?: ";
cin>>no_of_elements;
cout<<"Insert elementsay of element to sort: ";
for(int i=0;i
cin>>elements[i];
}
}

void MergeSort::partition(int elements[], int low, int high){
int mid;
if(low
mid=(low+high)/2;
partition(elements,low,mid);
partition(elements,mid+1,high);
sortit(elements,low,mid,high);
}
}

void MergeSort::sortit(int elements[], int low, int mid, int high){
int i,j,k,l,b;
l=low;
i=low;
j=mid+1;
while((l<=mid)&&(j<=high)){
if(elements[l]<=elements[j]){
b[i]=elements[l];
l++;
}else{
b[i]=elements[j];
j++;
}
i++;
}
if(l>mid){
for(k=j;k<=high;k++){
b[i]=elements[k];
i++;
}
}else{
for(k=l;k<=mid;k++){
b[i]=elements[k];
i++;
}
}
for(k=low;k<=high;k++){
elements[k]=b[k];
}
}

void MergeSort::display(){
cout<<"The sorted element is\n";
for(int i = 0 ; i < no_of_elements; i++){
cout< ";
}
}

int main(){
MergeSort MS;
MS.getarray();
MS.partition(MS.elements,0,MS.no_of_elements);
MS.display();
return 0;
}

Output:

How many elements? 7Insert element to sort: 63 78 52 12 99 32 13The sorted element is12 13 32 52 63 78 99
Efficiency of merge sort

Since the merge sort can not have more than logn passes and each pass involving ‘n’ or fewer comparisons, the merge sort requires no more than nlogn comparisons.  Hence the efficiency of merge sort is O(nlogn).

Related Posts October 7, 2012 Data Structure How to implement Shell Sort in C October 3, 2012 Data Structure How to implement Straight Insertion Sort in C October 4, 2012 Data Structure How to implement Straight Insertion Sort in C October 2, 2012 Data Structure How to implement Straight Selection Sort in C October 8, 2012 Data Structure Implementing Tree Sort in CZemanta

```