merge_sort.c

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

static void printAry(int* ary, int aryNum);
static void sort(int ary[], int left, int right);


int main (int argc, char *argv[]) {
  int ary[] = {8,4,3,7,6,5,2,1};
  const int aryNum = sizeof(ary) / sizeof(ary[0]);

  sort(ary, 0, aryNum - 1);
  printAry(ary, aryNum);

  return 0;
}

void sort(int ary[], int left, int right) {
  int i, j, k;
  if (left >= right) { return; }

  const int mid = (left + right) / 2;

  // recursion for split array
  sort(ary, left, mid);
  sort(ary, mid+1, right);

  // copy array to temp
  int* temp = (int *)malloc(sizeof(int) * (left+right));
  if (temp == NULL) { exit(0); }

  for (i = left; i <= mid ; i++) {
    temp[i] = ary[i];
  }

  // reverse
  for (i = mid+1, j = right; i <= right; i++, j--) {
    temp[i] = ary[j];
  }

  // merge sort
  i = left;
  j = right;
  for (k = left; k <= right; k++) {
    if (temp[i] <= temp[j]) {
      ary[k] = temp[i++];
    } else {
      ary[k] = temp[j--];
    }
  }
  return;
}

void printAry(int* ary, int aryNum) {
  int i;
  
  for (i = 0; i < aryNum; i++) {
    printf("%d ", ary[i]);
  }
  printf("\n");
}