Bucketsort_13513004

mergesort.c

+#include <stdlib.h>
+#include <mpi.h>
+#include <stdio.h>
+
+void merge(int* arr, int l, int m, int r, int* tmp) 
+{
+  int last = l;
+
+  // merge to tmp
+  int i = l, j = m;
+  for (; i < m && j < r;)
+  {
+    if (arr[i] > arr[j])
+      tmp[last++] = arr[j++];
+    else
+      tmp[last++] = arr[i++];
+  }
+  while (i < m) tmp[last++] = arr[i++];
+  while (j < r) tmp[last++] = arr[j++];
+
+  // move to origin
+  while (last > l) 
+  {
+    --last;
+    arr[last] = tmp[last];
+  }
+}
+
+void mergesort(int* arr, int l, int r, int* tmp) 
+{
+  if (l + 2 > r) return;      // base
+
+  int m = (l + r) >> 1;
+  mergesort(arr, l, m, tmp);
+  mergesort(arr, m, r, tmp);
+  merge(arr, l, m, r, tmp);
+}
+
+int main(int argc, char *argv[])
+{
+  int n, i;
+  scanf("%d", &n);
+
+  int *arr = (int*) malloc(sizeof(int) * (n + 1));
+  for (i = 0; i < 8; ++i)
+  {
+    scanf("%d", &arr[i]);
+  }
+
+  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);
+
+  int size = n / world_size;          // equally distributed
+  
+  int *arr_part = (int*) malloc(sizeof(int) * size);
+  MPI_Scatter(arr, size, MPI_INT, arr_part, size, MPI_INT, 0, MPI_COMM_WORLD);    // scatter to buckets
+  
+  int *tmp = (int*) malloc(sizeof(int) * size);
+  mergesort(arr_part, 0, size, tmp);
+  
+  int *sorted = NULL;
+  if(world_rank == 0) {
+    sorted = malloc(n * sizeof(int));
+  }
+  
+  MPI_Gather(arr_part, size, MPI_INT, sorted, size, MPI_INT, 0, MPI_COMM_WORLD);    // gather result
+  
+  if(world_rank == 0) 
+  {    
+    int *tmp2 = (int*) malloc(sizeof(int) * n);
+    mergesort(sorted, 0, n, tmp2);
+
+    for(i = 0; i < n; i++) 
+    {      
+      printf("%d ", sorted[i]);
+    }
+      
+    free(sorted);
+    free(tmp2);
+  }
+
+  free(arr);
+  free(arr_part);
+  free(tmp);
+
+  MPI_Barrier(MPI_COMM_WORLD);
+  MPI_Finalize();
+
+  return 0;
+}
\ No newline at end of file