mergesort.c

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

#define TABSIZE 1000

void print_array(int * array, int size) {
	for (int i=0; i<size; i++) {
		printf("%d ", array[i]);
	}
	puts("");
}

// Insertion sort

void shift(int * array, int start_index, int end_index) {
	for (int i=end_index; i>=start_index; i--) {
		array[i+1] = array[i];
	}
}

void insert(int * array, int end_index, int value) {
	int i = 0;
	while (i <= end_index && value > array[i]) {
		i++;
	}
	shift(array, i, end_index);
	array[i] = value;
}

int * insertion_sort(int * array, int size) {
	for (int i = 0; i<size-1; i++) {
		insert(array, i, array[i+1]);
	}
	return array;
}

int * init_array(int size) {
	int * t = malloc(size * sizeof(int));
	t[0] = 1;
	for (int i=1; i<size; i++) {
		t[i] = (2*t[i-1] + 1) % 37;
	}				
	return t;
}

// Merge sort

int * merge(int * array1, int size1, int * array2, int size2) {
	int * new_array = malloc(sizeof(int) * (size1 + size2));
	int i1=0, i2=0;
	for (int i=0; i<size1+size2; i++) { 
		if (i1==size1) {
			new_array[i] = array2[i2];
			i2++;
		} else if (i2==size2) {
			new_array[i] = array1[i1];
			i1++;
		} else if (array1[i1] <= array2[i2]) {
			new_array[i] = array1[i1];
			i1++;
		} else {
			new_array[i] = array2[i2];
			i2++;
		}
	}
	return new_array;
}

void split(int * array, int * first_half, int * second_half, int size_first_half, int size_second_half) {
	for (int i = 0; i<size_first_half; i++) {
		first_half[i] = array[i];
	}
	for (int i = 0; i<size_second_half ; i++) {
		second_half[i] = array[size_first_half + i];
	}
}

int * mergesort(int * array, int size) {
	if (size == 1) {
		int * res = malloc(sizeof(int));
		*res = array[0];
		return res;
	}
	int h = size / 2;
	int * fh = malloc(h * sizeof(int));
	int * sh = malloc((size-h) * sizeof(int));
	split(array, fh, sh, h, size-h);
	int * t1 = mergesort(fh, h);
	int * t2 = mergesort(sh, size-h);
	free(sh);
	free(fh);
	int * m = merge(t1, h, t2, size-h);
	free(t1);
	free(t2);
	return m;
}

int main () {
	int * array = init_array(TABSIZE);
	int * result = mergesort(array, TABSIZE);
	print_array(result, TABSIZE);
	free(array);
	free(result);
}