blogs-2023-09

perf.c

// simple code to benchmark the sort
long time_it(void (*f)(int *, int), int *arr, int n) {
  struct timespec start, end;
  clock_gettime(CLOCK_MONOTONIC, &start);
  f(arr, n);
  clock_gettime(CLOCK_MONOTONIC, &end);
  long diff = (end.tv_sec - start.tv_sec) * 1e9;
  diff += (end.tv_nsec - start.tv_nsec);
  return diff;
}

xmerge.c

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

#define CUT_OFF 128

void exch(int *a, int i, int j) {
  int swap = a[i];
  a[i] = a[j];
  a[j] = swap;
}

void insertion_sort(int *arr, int lo, int hi) {
  for (int i = lo + 1; i <= hi; i++) {
    for (int j = i; j > lo && arr[j] < arr[j - 1]; j--) {
      exch(arr, j, j - 1);
    }
  }
}

void merge(int *src, int *dst, int lo, int mid, int hi) {
  int i = lo, j = mid + 1;
  for (int k = lo; k <= hi; k++) {
    if (i > mid) {
      dst[k] = src[j++];
    } else if (j > hi) {
      dst[k] = src[i++];
    } else if (src[j] < src[i]) {
      dst[k] = src[j++];
    } else {
      dst[k] = src[i++];
    }
  }
}

void merge_sort(int *src, int *dst, int lo, int hi) {
  if (hi <= lo + CUT_OFF) {
    insertion_sort(dst, lo, hi);
    return;
  }
  int mid = lo + (hi - lo) / 2;
  merge_sort(dst, src, lo, mid);
  merge_sort(dst, src, mid + 1, hi);
  if (src[mid] <= src[mid + 1]) {
    memcpy(dst + lo, src + lo, (hi - lo + 1) * sizeof(int));
    return;
  }
  merge(src, dst, lo, mid, hi);
}

void xsort(int *arr, int len) {
  int *aux = malloc(len * sizeof(int));
  memcpy(aux, arr, len * sizeof(int));
  merge_sort(aux, arr, 0, len - 1);
  free(aux);
}