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

#define MAX_NUMBER 100
#define LIST_SIZE 10

int compareCounter = 0;

int compare(int a, int b) {
	compareCounter++;
	return a - b;
}

int* generateRandomList(int size) {
	int* list = malloc(sizeof(int)*size);
	int i;
	for (i=0; i<size; i++) {
		list[i] = rand() % MAX_NUMBER;
	}
	return list;
}

void printList(int* list,int size) {
	int i;
	for (i=0; i<size; i++) {
		printf("%d ",list[i]);
	}
	printf("\n");
}

int* merge(int* list1,int* list2,int size1,int size2){
	int mergedSize = size1 + size2;
	int* mergedList = malloc(sizeof(int)*mergedSize);
	int i1=0,i2=0,i3=0;
	for (i3=0;i3<mergedSize;i3++) {
		// VUL HIER AAN!
		if(list1[i1] > list2[i2])
		{
			//If its bigger then we dont put the list 1 value but we take the list 2 value and we increment list 2
			mergedList[i3] = list2[i2];
			i2++;
		} else if(list1[i1] < list2[i2]) {
			mergedList[i3] = list1[i1];
			i1++;
		} else {
			//Its equal
			mergedList[i3] = list2[i2];
			i2++;
		}
	}
	return mergedList;
}

void mergeSort(int *list,int size) {
	if (size<=1) return;
	int* list1 = list;
	int* list2 = list + size/2;
	int size1 = size/2;
	int size2 = size - size/2;
	mergeSort(list1, size1);
	mergeSort(list2, size2);
	int* list3 = merge(list1, list2, size1, size2);
	int i;
	for(i=0; i<size; i++) {
		list[i] = list3[i];
	}
}

int main(int argc, char **argv) {
	srand(time(NULL));
	int size;
	int *lijst = generateRandomList(LIST_SIZE);
	printf("Lijst : ");
	printList(lijst,LIST_SIZE);
	mergeSort(lijst, LIST_SIZE);
	printf("Merged:  ");
	printList(lijst,LIST_SIZE);
	return 0;
}