mrgsort.c

#include <stdio.h>
#include <string.h>

static void p(int xs[], int s, int e) {
  int i;

  printf("[");
  for (i = s; i <= e; i++) {
    printf("%d ", xs[i]);
  }
  printf("]\n");
}

static void sort(int xs[], int work[], int start, int end) {
  int len = end - start + 1;
  int mid = start + len / 2;

  // printf("sort: s:%d, e:%d, l:%d, m:%d\n", start, end, len, mid);
  if (len <= 1)
    return;

  sort(xs, work, start, mid - 1);
  sort(xs, work, mid, end);

  {
    int i = 0;
    int a = start;
    int b = mid;
    // printf("------------- s:%d, e:%d -------------\n", start, end);
    while (i < len) {
      if (a < mid && (b > end || xs[a] < xs[b]))
        work[i++] = xs[a++];
      else
        work[i++] = xs[b++];
    }
    memcpy(xs + start, work, sizeof(xs[0]) * len);
  }
}

void main(void) {
  int xs[] = { 7, 3, 9, 1, 0, 8, 2, 5, 6, 4 }; 
  int len = sizeof(xs)/sizeof(xs[0]);
  int work[len];

  sort(xs, work, 0, len - 1);
  p(xs, 0, len - 1);
}