mergesort implementation in C

makefile

CFLAGS=-std=c11 -g -Wall -Wextra -pedantic
mergesort:

mergesort.c

// Max DeLiso <[email protected]>
// mergesort implementation in C11
// 5/11/17

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

#define NUM_TRIALS 10
#define NUM_INTS  25
#define MAX_RANGE 10

#define MAX(a,b) (a>b)?(a):(b)
#define MIN(a,b) (a<b)?(a):(b)

void print_list(const int * const xs,
                const int length);

void merge(int * xs,
           int * buffer,
           const int fst,
           const int snd,
           const int rgt);

void mergesort_splitter(int * xs,
                        int * buffer,
                        const int length,
                        int lft,
                        int rgt);

void mergesort(int * xs,
               const int length);

bool is_sorted(const int * const xs,
               const int length);

int main() {
  srand(time(NULL));
  int xs [NUM_INTS] = {0}; 

  for(int i = 0; i < NUM_TRIALS; i++) {
    for(int j = 0; j < NUM_INTS; j++) {
      xs[j] = rand() % MAX_RANGE + 1;
    }
      
    print_list(xs, NUM_INTS);
    mergesort(xs, NUM_INTS);
    print_list(xs, NUM_INTS);
    bool sorted = is_sorted(xs, NUM_INTS);
    assert(sorted);
    printf("\n");
  }

  return 0;
}

void print_list(const int * const xs,
                const int length) {
  for(int i = 0; i < length; i++) {
    printf("%3i", xs[i]);

    const bool is_last = (i == length - 1);
    if(!is_last) { printf(" "); }
  }
  printf("\n");
}

void merge(int * xs,
           int * buffer,
           const int fst,
           const int snd,
           const int rgt) {
  int i = fst;
  int j = snd;
  int k = 0;
  const int span = rgt - fst + 1;

  assert(xs != NULL);
  assert(buffer != NULL);
  assert(fst <= snd);
  assert(fst >= 0);
  assert(snd >= 0);
  assert(snd <= rgt);
  assert(fst <= rgt);

  while(i < snd && j <= rgt) {
   if(xs[i] < xs[j]) {
     buffer[k++] = xs[i++];
   } else {
     buffer[k++] = xs[j++];
   }
  }

  while(i < snd) {
    buffer[k++] = xs[i++];
  }

  while(j <= rgt) {
    buffer[k++] = xs[j++];
  }

  // copy back into xs from buffer, starting from lft
  memcpy(xs + fst, buffer, span * sizeof(int));
}

void mergesort_splitter(int * xs,
                        int * buffer,
                        const int length,
                        int lft,
                        int rgt) {
  assert(lft >= 0);
  assert(lft <= rgt);
  assert(rgt <= length - 1);

  int sub_list_length = rgt - lft + 1;

  if(sub_list_length == 0 || sub_list_length == 1) {
    return;
  } else if(sub_list_length == 2) {
    int lft_val = xs[lft];
    int rgt_val = xs[lft + 1];

    int max_of_pair = MAX(lft_val, rgt_val);
    int min_of_pair = MIN(lft_val, rgt_val);

    xs[lft] = min_of_pair;
    xs[lft + 1] = max_of_pair;
  } else {
    const int mid = (lft + rgt) / 2;
    const int fst = lft;
    const int snd = mid + 1;

    mergesort_splitter(xs, buffer, length, lft, mid);
    mergesort_splitter(xs, buffer, length, mid + 1, rgt);
    merge(xs, buffer, fst, snd, rgt);
  }
}

void mergesort(int * xs,
               const int length) {
  int xs_buffer [length];
  mergesort_splitter(xs, xs_buffer, length, 0, length - 1);
}

bool is_sorted(const int * const xs,
               const int length) {
  for(int i = 0; i < length - 1; i++) {
    if(xs[i] > xs[i+1]) {
      return false;
    }
  }
  return true;
}