Labels

algorithms (22) Design Patterns (20) java (19) linux (14) Snippet (13) service mix (6) soa (4)

Merge Sort

Merge sort in C


#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);
}

1 comment:

Search 24 Bytes

Loading...