Merge Sort in C++

by Sandeep on July 20, 2009

Merge sort is an O(n log n) comparison-based sorting algorithm. In most implementations it is stable, meaning that it preserves the input order of equal elements in the sorted output.
It is an example of the divide and conquer algorithmic paradigm.
Program:

#include < iostream.h >
#include < conio.h >
#include < stdio.h >

void print(int * a) {
for (int i = 0; i < 10; i++) {
cout << a[i] << “-”;
}
cout << endl;
}

void mergeConquer(int * a, int left, int mid, int right) {
int lno = mid – left + 1;
int rno = right – mid;
int * L = new int[lno];
int * R = new int[rno];

for (int y = 0; y < lno; y++) {
L[y] = a[left + y];
cout << L[y] << “l”;
}
cout << endl;
for (int z = 0; z < rno; z++) {
R[z] = a[mid + z + 1];
cout << R[z] << ” r “; ;
}
cout << endl;
y = 0;
z = 0;

for (int i = left; i <= right; i++) {
if ( (y < lno) && (z < rno)) {
if (L[y] <= R[z]) {
a[i] = L[y];
y++;
}
else {
a[i] = R[z];
z++;
}
}
else if ( (y < lno) && (z >= rno)) {
a[i] = L[y];
y++;
}
else if ( (y >= lno) && (z < rno)) {
a[i] = R[z];
z++;
}

}

}

void mergeDivide(int * a, int left, int right) {
int mid = (left + right) / 2;
if (left < right) {
cout << “============”;
mergeDivide(a, left, mid);
mergeDivide(a, mid + 1, right);
mergeConquer(a, left, mid, right);
}

}

void main() {
clrscr();
int a[] = {
5, 24, 6, 48, 9, 40, 42, 3, 1, 7};
mergeDivide(a, 0, 9);
print(a);
}

if you find any bug in the above program. let us know about it. Please post your complaint at pctech@gadgetcage.com.

ADVERTISEMENT

We'll send more interesting posts like Merge Sort in C++ to you!
Enter your Email Address:
Join us on Facebook.

  HostGator
    

Leave a Comment

Previous post:

Next post: