fork download
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4. #include <mpi.h>
  5.  
  6. void merge(int *, int *, int, int, int);
  7. void mergeSort(int *, int *, int, int);
  8.  
  9. int main(int argc, char** argv) {
  10.  
  11. /********** Create and populate the array **********/
  12. int n = atoi(argv[1]);
  13. int *original_array = malloc(n * sizeof(int));
  14.  
  15. int c;
  16. srand(time(NULL));
  17. printf("This is the unsorted array: ");
  18. for(c = 0; c < n; c++) {
  19.  
  20. original_array[c] = rand() % n;
  21. printf("%d ", original_array[c]);
  22.  
  23. }
  24.  
  25. printf("\n");
  26. printf("\n");
  27.  
  28. /********** Initialize MPI **********/
  29. int world_rank;
  30. int world_size;
  31.  
  32. MPI_INIT(&argc, &argv);
  33. MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);
  34. MPI_Comm_size(MPI_COMM_WORLD, &world_size);
  35.  
  36. /********** Divide the array in equal-sized chunks **********/
  37. int size = n/world_size;
  38.  
  39. /********** Send each subarray to each process **********/
  40. int *sub_array = malloc(size * sizeof(int));
  41. MPI_Scatter(original_array, size, MPI_INT, sub_array, size, MPI_INT, 0, MPI_COMM_WORLD);
  42.  
  43. /********** Perform the mergesort on each process **********/
  44. int *tmp_array = malloc(size * sizeof(int));
  45. mergeSort(sub_array, tmp_array, 0, (size - 1));
  46.  
  47. /********** Gather the sorted subarrays into one **********/
  48. int *sorted = NULL;
  49. if(world_rank == 0) {
  50.  
  51. sorted = malloc(n * sizeof(int));
  52.  
  53. }
  54.  
  55. MPI_Gather(sub_array, size, MPI_INT, sorted, size, MPI_INT, 0, MPI_COMM_WORLD);
  56.  
  57. /********** Make the final mergeSort call **********/
  58. if(world_rank == 0) {
  59.  
  60. int *other_array = malloc(n * sizeof(int));
  61. mergeSort(sorted, other_array, 0, (n - 1));
  62.  
  63. /********** Display the sorted array **********/
  64. printf("This is the sorted array: ");
  65. for(c = 0; c < n; c++) {
  66.  
  67. printf("%d ", sorted[c]);
  68.  
  69. }
  70.  
  71. printf("\n");
  72. printf("\n");
  73.  
  74. /********** Clean up root **********/
  75. free(sorted);
  76. free(other_array);
  77.  
  78. }
  79.  
  80. /********** Clean up rest **********/
  81. free(original_array);
  82. free(sub_array);
  83. free(tmp_array);
  84.  
  85. /********** Finalize MPI **********/
  86. MPI_Barrier(MPI_COMM_WORLD);
  87. MPI_Finalize();
  88.  
  89. }
  90.  
  91. /********** Merge Function **********/
  92. void merge(int *a, int *b, int l, int m, int r) {
  93.  
  94. int h, i, j, k;
  95. h = l;
  96. i = l;
  97. j = m + 1;
  98.  
  99. while((h <= m) && (j <= r)) {
  100.  
  101. if(a[h] <= a[j]) {
  102.  
  103. b[i] = a[h];
  104. h++;
  105.  
  106. }
  107.  
  108. else {
  109.  
  110. b[i] = a[j];
  111. j++;
  112.  
  113. }
  114.  
  115. i++;
  116.  
  117. }
  118.  
  119. if(m < h) {
  120.  
  121. for(k = j; k <= r; k++) {
  122.  
  123. b[i] = a[k];
  124. i++;
  125.  
  126. }
  127.  
  128. }
  129.  
  130. else {
  131.  
  132. for(k = h; k <= m; k++) {
  133.  
  134. b[i] = a[k];
  135. i++;
  136.  
  137. }
  138.  
  139. }
  140.  
  141. for(k = l; k <= r; k++) {
  142.  
  143. a[k] = b[k];
  144.  
  145. }
  146.  
  147. }
  148.  
  149. /********** Recursive Merge Function **********/
  150. void mergeSort(int *a, int *b, int l, int r) {
  151.  
  152. int m;
  153.  
  154. if(l < r) {
  155.  
  156. m = (l + r)/2;
  157.  
  158. mergeSort(a, b, l, m);
  159. mergeSort(a, b, (m + 1), r);
  160. merge(a, b, l, m, r);
  161.  
  162. }
  163.  
  164. }
Success #stdin #stdout #stderr 0.26s 39076KB
stdin
Standard input is empty
stdout
Standard output is empty
stderr
Error: unexpected symbol in "void merge"
Execution halted