mergesort

makefile

CFLAGS=-Wall -Wextra -pedantic -std=c11
CC=clang
OUT=mergesort

$(OUT): $(OUT).c makefile
	$(CC) $(CFLAGS) $< -o $(OUT)

clean:
	$(RM) $(OUT)

mergesort.c

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

int max(const int a, const int b);
int min(const int a, const int b);
void mergesort(int xs[], const int n);
void mergesort_rec(int xs[], int scratch[], const int lft, const int rgt);
void combine(int xs[], int scratch[], const int lft, const int mid, const int rgt);
void print_array(const int xs[], const int len);

int main() {
  int n;
  int * xs = NULL;

  while (true) {
    printf("n: ");

    if (scanf("%i", &n) != 1) {
      break;
    }

    xs = malloc(n * sizeof(int));

    if (xs == NULL) {
      break;
    }

    for(int i = 0; i < n; i++) {
      if (scanf("%i", &xs[i]) != 1) {
        break;
      }
    }

    print_array(xs, n);
    mergesort(xs, n);
    print_array(xs, n);

    printf("\n");
    free(xs);
    xs = NULL;
  }

  return 0;
}

int max(const int a, const int b) {
  if (a > b) return a;
  else return b;
}

int min(const int a, const int b) {
  if (a < b) return a;
  else return b;
}

void mergesort(int xs[], const int n) {
  int * scratch = malloc(n * sizeof(int));
  mergesort_rec(xs, scratch, 0, n - 1);
  free(scratch);
}

void mergesort_rec(int xs[], int scratch[], const int lft, const int rgt) {
  const int len = rgt - lft + 1;

  if (len <= 1) {
    return;
  }

  if (len == 2) {
    int a = min(xs[lft], xs[rgt]);
    int b = max(xs[lft], xs[rgt]);
    xs[lft] = a;
    xs[rgt] = b;
    return;
  }

  int mid = (lft + rgt) / 2;
  mergesort_rec(xs, scratch, lft, mid);
  mergesort_rec(xs, scratch, mid + 1, rgt);
  combine(xs, scratch, lft, mid, rgt);
}

void combine(int xs[], int scratch[], const int lft, const int mid, const int rgt) {
  const int len = rgt - lft + 1;

  int lftHead;
  int rgtHead;
  int scratchHead;

  for (lftHead = lft,
       rgtHead = mid + 1,
       scratchHead = 0;
       lftHead <= mid &&
       rgtHead <= rgt &&
       scratchHead < len;
       scratchHead++) {
    if (xs[lftHead] < xs[rgtHead]) {
      scratch[scratchHead] = xs[lftHead++];
    } else {
      scratch[scratchHead] = xs[rgtHead++];
    }
  }

  while (lftHead <= mid) {
    scratch[scratchHead++] = xs[lftHead++];
  }

  while (rgtHead <= rgt) {
    scratch[scratchHead++] = xs[rgtHead++];
  }

  for (int scanHead = 0,
       writeHead = lft;
       scanHead < len;
       scanHead++,
       writeHead++) {
    xs[writeHead] = scratch[scanHead];
  }
}

void print_array(const int xs[], const int len) {
  for(int i = 0; i < len; i++) {
    printf("%i ", xs[i]);
  }

  printf("\n");
}