merge_sort_openmp_task.c

#include <stdlib.h>
#include <stdio.h>

#include <time.h>
#include <sys/time.h>
#include <math.h>

#define N 2097152

double wall_time(void) {
  struct timeval tv;
  struct timezone tz;

  gettimeofday(&tv, &tz);
  return(tv.tv_sec + tv.tv_usec/1000000.0);
}


void print_array(int* array, int l, int r) {
  int i;

  printf("[");
  for (i = l; i <= r; i++) {
    printf("%d", array[i]);
    if (i != r) {
      printf(", ");
    }
  }
  printf("]\n");
}

/*
 * Merges two sorted pieces from *array:
 * [sl, el] and [sr, er]
 */
void merge(int* array, int sl, int el, int sr, int er) {
  int len_l = el - sl + 1;
  int len_r = er - sr + 1;

  int pos = 0;

  // Creates a buffer to store the sorted interval temporarily
  // It is not possible to sort two sorted arrays in O(n) without additional memory
  int* buffer = (int*) malloc((len_l + len_r) * sizeof(int));

  while (sl <= el && sr <= er) {
    if (array[sl] <= array[sr]) {
      buffer[pos++] = array[sl++];
    } else {
      buffer[pos++] = array[sr++];
    }
  }

  while (sl <= el) {
    buffer[pos++] = array[sl++];
  }
  while (sr <= er) {
    buffer[pos++] = array[sr++];
  }

  sl -= len_l;
  sr -= len_r;

  for (pos = 0; pos < len_l; pos++) {
    array[sl++] = buffer[pos];
  }
  for (pos = len_l; pos < len_l + len_r; pos++) {
    array[sr++] = buffer[pos];
  }

  free(buffer);
}

void merge_sort(int* array, int begin, int end) {
  if (end - begin + 1 <= 1) return;

  int m = (begin + end) / 2;

  #pragma omp task
  merge_sort(array, begin, m);

  #pragma omp task
  merge_sort(array, m + 1, end);

  #pragma omp taskwait
  merge(array, begin, m, m + 1, end);
}

int is_sorted(int* array, int len) {
  int i;
  for (i = 1; i < len; i++) {
    if (array[i] < array[i - 1]) {
      return 0;
    }
  }
  return 1;
}

int omp_thread_count() {
  int n = 0;
  #pragma omp parallel reduction(+:n)
  n += 1;
  return n;
}
int main() {
  int i;
  int* array = (int*) malloc(N * sizeof(int));

  if (!array) {
    printf("Panic. Could not allocate memory for array\n");
  }

  srand(time(NULL));
  for (i = 0; i < N; i++) {
    array[i] = rand() % N;
  }

  printf("%d\n", omp_thread_count());

  //print_array(array, 0, N - 1);
  double t0 = wall_time();
  merge_sort(array, 0, N - 1);
  double t1 = wall_time();
  //print_array(array, 0, N - 1);

  printf("Time spent %.4lf\n", t1 - t0);

  if (!is_sorted(array, N)) {
    printf("Failure, the algorithm is not sorting properly.\n");
  } else {
    printf("Array successfuly sorted\n");
  }

  free(array);

  return 0;
}