#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <mpi.h>
void merge(int *, int *, int, int, int);
void mergeSort(int *, int *, int, int);
int main(int argc, char** argv) {
/********** Create and populate the array **********/
int *original_array
= malloc(n
* sizeof(int));
int c;
printf("This is the unsorted array: "); for(c = 0; c < n; c++) {
original_array
[c
] = rand() % n
; printf("%d ", original_array
[c
]);
}
/********** Initialize MPI **********/
int world_rank;
int world_size;
MPI_INIT(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);
MPI_Comm_size(MPI_COMM_WORLD, &world_size);
/********** Divide the array in equal-sized chunks **********/
int size = n/world_size;
/********** Send each subarray to each process **********/
int *sub_array
= malloc(size
* sizeof(int)); MPI_Scatter(original_array, size, MPI_INT, sub_array, size, MPI_INT, 0, MPI_COMM_WORLD);
/********** Perform the mergesort on each process **********/
int *tmp_array
= malloc(size
* sizeof(int)); mergeSort(sub_array, tmp_array, 0, (size - 1));
/********** Gather the sorted subarrays into one **********/
int *sorted = NULL;
if(world_rank == 0) {
sorted
= malloc(n
* sizeof(int));
}
MPI_Gather(sub_array, size, MPI_INT, sorted, size, MPI_INT, 0, MPI_COMM_WORLD);
/********** Make the final mergeSort call **********/
if(world_rank == 0) {
int *other_array
= malloc(n
* sizeof(int)); mergeSort(sorted, other_array, 0, (n - 1));
/********** Display the sorted array **********/
printf("This is the sorted array: "); for(c = 0; c < n; c++) {
}
/********** Clean up root **********/
}
/********** Clean up rest **********/
/********** Finalize MPI **********/
MPI_Barrier(MPI_COMM_WORLD);
MPI_Finalize();
}
/********** Merge Function **********/
void merge(int *a, int *b, int l, int m, int r) {
int h, i, j, k;
h = l;
i = l;
j = m + 1;
while((h <= m) && (j <= r)) {
if(a[h] <= a[j]) {
b[i] = a[h];
h++;
}
else {
b[i] = a[j];
j++;
}
i++;
}
if(m < h) {
for(k = j; k <= r; k++) {
b[i] = a[k];
i++;
}
}
else {
for(k = h; k <= m; k++) {
b[i] = a[k];
i++;
}
}
for(k = l; k <= r; k++) {
a[k] = b[k];
}
}
/********** Recursive Merge Function **********/
void mergeSort(int *a, int *b, int l, int r) {
int m;
if(l < r) {
m = (l + r)/2;
mergeSort(a, b, l, m);
mergeSort(a, b, (m + 1), r);
merge(a, b, l, m, r);
}
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPHRpbWUuaD4KI2luY2x1ZGUgPG1waS5oPgoKdm9pZCBtZXJnZShpbnQgKiwgaW50ICosIGludCwgaW50LCBpbnQpOwp2b2lkIG1lcmdlU29ydChpbnQgKiwgaW50ICosIGludCwgaW50KTsKCmludCBtYWluKGludCBhcmdjLCBjaGFyKiogYXJndikgewoJCgkvKioqKioqKioqKiBDcmVhdGUgYW5kIHBvcHVsYXRlIHRoZSBhcnJheSAqKioqKioqKioqLwoJaW50IG4gPSBhdG9pKGFyZ3ZbMV0pOwoJaW50ICpvcmlnaW5hbF9hcnJheSA9IG1hbGxvYyhuICogc2l6ZW9mKGludCkpOwoJCglpbnQgYzsKCXNyYW5kKHRpbWUoTlVMTCkpOwoJcHJpbnRmKCJUaGlzIGlzIHRoZSB1bnNvcnRlZCBhcnJheTogIik7Cglmb3IoYyA9IDA7IGMgPCBuOyBjKyspIHsKCQkKCQlvcmlnaW5hbF9hcnJheVtjXSA9IHJhbmQoKSAlIG47CgkJcHJpbnRmKCIlZCAiLCBvcmlnaW5hbF9hcnJheVtjXSk7CgkJCgkJfQoKCXByaW50ZigiXG4iKTsKCXByaW50ZigiXG4iKTsKCQoJLyoqKioqKioqKiogSW5pdGlhbGl6ZSBNUEkgKioqKioqKioqKi8KCWludCB3b3JsZF9yYW5rOwoJaW50IHdvcmxkX3NpemU7CgkKCU1QSV9JTklUKCZhcmdjLCAmYXJndik7CglNUElfQ29tbV9yYW5rKE1QSV9DT01NX1dPUkxELCAmd29ybGRfcmFuayk7CglNUElfQ29tbV9zaXplKE1QSV9DT01NX1dPUkxELCAmd29ybGRfc2l6ZSk7CgkJCgkvKioqKioqKioqKiBEaXZpZGUgdGhlIGFycmF5IGluIGVxdWFsLXNpemVkIGNodW5rcyAqKioqKioqKioqLwoJaW50IHNpemUgPSBuL3dvcmxkX3NpemU7CgkKCS8qKioqKioqKioqIFNlbmQgZWFjaCBzdWJhcnJheSB0byBlYWNoIHByb2Nlc3MgKioqKioqKioqKi8KCWludCAqc3ViX2FycmF5ID0gbWFsbG9jKHNpemUgKiBzaXplb2YoaW50KSk7CglNUElfU2NhdHRlcihvcmlnaW5hbF9hcnJheSwgc2l6ZSwgTVBJX0lOVCwgc3ViX2FycmF5LCBzaXplLCBNUElfSU5ULCAwLCBNUElfQ09NTV9XT1JMRCk7CgkKCS8qKioqKioqKioqIFBlcmZvcm0gdGhlIG1lcmdlc29ydCBvbiBlYWNoIHByb2Nlc3MgKioqKioqKioqKi8KCWludCAqdG1wX2FycmF5ID0gbWFsbG9jKHNpemUgKiBzaXplb2YoaW50KSk7CgltZXJnZVNvcnQoc3ViX2FycmF5LCB0bXBfYXJyYXksIDAsIChzaXplIC0gMSkpOwoJCgkvKioqKioqKioqKiBHYXRoZXIgdGhlIHNvcnRlZCBzdWJhcnJheXMgaW50byBvbmUgKioqKioqKioqKi8KCWludCAqc29ydGVkID0gTlVMTDsKCWlmKHdvcmxkX3JhbmsgPT0gMCkgewoJCQoJCXNvcnRlZCA9IG1hbGxvYyhuICogc2l6ZW9mKGludCkpOwoJCQoJCX0KCQoJTVBJX0dhdGhlcihzdWJfYXJyYXksIHNpemUsIE1QSV9JTlQsIHNvcnRlZCwgc2l6ZSwgTVBJX0lOVCwgMCwgTVBJX0NPTU1fV09STEQpOwoJCgkvKioqKioqKioqKiBNYWtlIHRoZSBmaW5hbCBtZXJnZVNvcnQgY2FsbCAqKioqKioqKioqLwoJaWYod29ybGRfcmFuayA9PSAwKSB7CgkJCgkJaW50ICpvdGhlcl9hcnJheSA9IG1hbGxvYyhuICogc2l6ZW9mKGludCkpOwoJCW1lcmdlU29ydChzb3J0ZWQsIG90aGVyX2FycmF5LCAwLCAobiAtIDEpKTsKCQkKCQkvKioqKioqKioqKiBEaXNwbGF5IHRoZSBzb3J0ZWQgYXJyYXkgKioqKioqKioqKi8KCQlwcmludGYoIlRoaXMgaXMgdGhlIHNvcnRlZCBhcnJheTogIik7CgkJZm9yKGMgPSAwOyBjIDwgbjsgYysrKSB7CgkJCQoJCQlwcmludGYoIiVkICIsIHNvcnRlZFtjXSk7CgkJCQoJCQl9CgkJCQoJCXByaW50ZigiXG4iKTsKCQlwcmludGYoIlxuIik7CgkJCQoJCS8qKioqKioqKioqIENsZWFuIHVwIHJvb3QgKioqKioqKioqKi8KCQlmcmVlKHNvcnRlZCk7CgkJZnJlZShvdGhlcl9hcnJheSk7CgkJCQoJCX0KCQoJLyoqKioqKioqKiogQ2xlYW4gdXAgcmVzdCAqKioqKioqKioqLwoJZnJlZShvcmlnaW5hbF9hcnJheSk7CglmcmVlKHN1Yl9hcnJheSk7CglmcmVlKHRtcF9hcnJheSk7CgkKCS8qKioqKioqKioqIEZpbmFsaXplIE1QSSAqKioqKioqKioqLwoJTVBJX0JhcnJpZXIoTVBJX0NPTU1fV09STEQpOwoJTVBJX0ZpbmFsaXplKCk7CgkKCX0KCi8qKioqKioqKioqIE1lcmdlIEZ1bmN0aW9uICoqKioqKioqKiovCnZvaWQgbWVyZ2UoaW50ICphLCBpbnQgKmIsIGludCBsLCBpbnQgbSwgaW50IHIpIHsKCQoJaW50IGgsIGksIGosIGs7CgloID0gbDsKCWkgPSBsOwoJaiA9IG0gKyAxOwoJCgl3aGlsZSgoaCA8PSBtKSAmJiAoaiA8PSByKSkgewoJCQoJCWlmKGFbaF0gPD0gYVtqXSkgewoJCQkKCQkJYltpXSA9IGFbaF07CgkJCWgrKzsKCQkJCgkJCX0KCQkJCgkJZWxzZSB7CgkJCQoJCQliW2ldID0gYVtqXTsKCQkJaisrOwoJCQkKCQkJfQoJCQkKCQlpKys7CgkJCgkJfQoJCQoJaWYobSA8IGgpIHsKCQkKCQlmb3IoayA9IGo7IGsgPD0gcjsgaysrKSB7CgkJCQoJCQliW2ldID0gYVtrXTsKCQkJaSsrOwoJCQkKCQkJfQoJCQkKCQl9CgkJCgllbHNlIHsKCQkKCQlmb3IoayA9IGg7IGsgPD0gbTsgaysrKSB7CgkJCQoJCQliW2ldID0gYVtrXTsKCQkJaSsrOwoJCQkKCQkJfQoJCQkKCQl9CgkJCglmb3IoayA9IGw7IGsgPD0gcjsgaysrKSB7CgkJCgkJYVtrXSA9IGJba107CgkJCgkJfQoJCQoJfQoKLyoqKioqKioqKiogUmVjdXJzaXZlIE1lcmdlIEZ1bmN0aW9uICoqKioqKioqKiovCnZvaWQgbWVyZ2VTb3J0KGludCAqYSwgaW50ICpiLCBpbnQgbCwgaW50IHIpIHsKCQoJaW50IG07CgkKCWlmKGwgPCByKSB7CgkJCgkJbSA9IChsICsgcikvMjsKCQkKCQltZXJnZVNvcnQoYSwgYiwgbCwgbSk7CgkJbWVyZ2VTb3J0KGEsIGIsIChtICsgMSksIHIpOwoJCW1lcmdlKGEsIGIsIGwsIG0sIHIpOwoJCQoJCX0KCQkKCX0=