gistfile1.txt

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

void merge(int *array,const int p, const int q,const int r) {
  int n1 = q-p;
  int n2 = r-q;
  int *left = malloc((n1)*sizeof(int));
  int *right = malloc((n2)*sizeof(int));
  int i,j,k;
  for(i = 0; i < n1; i++) left[i] = array[p+i];
  for(i = 0; i < n2; i++) right[i] = array[q+i];
  i = 0;
  j = 0;
  for(k = p; k < r; k++) {
    if((j < n2 && i < n1 && left[i] <= right[j]) || (j >= n2 && i < n1)) {
      array[k] = left[i];
      i++;
    } else {    
      if(j < n2) array[k] = right[j];
      j++;
    }
  }
}


void merge_sort(int *array,const int p,const int r) {
  if(p < r-1) {
    const int q = (p+r)/2;
    merge_sort(array,p,q);
    merge_sort(array,q,r);
    merge(array,p,q,r);
  }
}

int main() {
  int i;
  int a[] = {10,4,67,12,12,16,9,1,4,5,11,23,13,10,14,5,4,100};
  const int length = sizeof(a)/sizeof(int);
  merge_sort(a,0,length);
  for(i = 0 ; i < length; i++) printf("%d ",a[i]);
  printf("\n");
  return 0;
}