merge sort dissection

merge_sort

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

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

#define N 10000000

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 len) {
  int i, j;

  /*
   * `i` Represents the size of a block compared.
   * It goes from 1 to the largest possible value smaller than N.
   * It grows as a power of 2 (due to the bitwise operation << ).
   */
  for (i = 1; i < len; i <<= 1) {
    /*
     * Now merging the sorted intervals [j, j + i - 1], [j + i, j + 2 * i - 1].
     */
    #pragma omp parallel for
    for (j = 0; j < len; j += 2 * i) {
      int start_l = j;
      int end_l = fmin(len - 1, j + i - 1);

      int start_r = end_l + 1;
      int end_r = fmin(len - 1, j + 2 * i - 1);

      merge(array, start_l, end_l, start_r, end_r);
    }
  }
}

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

  //print_array(array, 0, N - 1);
  double t0 = wall_time();
  merge_sort(array, N);
  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;
}