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

struct ArrayList {
    unsigned short * array;
    unsigned size;
};


struct ArrayList * generateRandomData(unsigned size, unsigned seed) {
	srand(seed);
	struct ArrayList *lista = (struct ArrayList *)malloc(sizeof(struct ArrayList));
	unsigned int j;
	lista -> array = (unsigned short *) malloc(size * sizeof(unsigned short));
	lista -> size = size;
	for(j = 0; j < size; j++) {
		lista -> array[j] = (unsigned short)rand();
	}
	return lista;
}

struct ArrayList * arrayListClone(struct ArrayList * list) {
	struct ArrayList *clona = (struct ArrayList*)malloc(sizeof(struct ArrayList));
	int j;
	clona -> array = (unsigned short*) malloc(list->size * sizeof(unsigned short));
	for(j = 0; j < list -> size; j++) {
		clona -> array[j] = list -> array[j];
	}
	clona -> size = list -> size;
	return clona;
	
}

unsigned long arrayListBubbleSort(struct ArrayList * list) {
	int finish;
	unsigned timeSpent;
	clock_t begin, end;
	begin = clock();
	do {
		finish = 1;
		unsigned i;
		for(i = 0; i < list -> size - 1; i++) {
			if(list -> array[i] > list -> array[i + 1]) {
				unsigned short tmp = list -> array[i];
				list -> array[i] = list -> array[i + 1];
				list -> array[i + 1] = tmp;
				finish = 0;
			}
		}
	}while(!finish); 
  	

	end = clock();
	timeSpent = (end - begin) / (CLOCKS_PER_SEC / 1000);

	return timeSpent;
}

void mergeSortSplit(unsigned short *array, unsigned size);

void mergeSortSplit(unsigned short *array, unsigned size) {
    if (size < 2)
        return;
    int mid = size / 2;
    mergeSortSplit(array, mid);
    mergeSortSplit(array + mid, size - mid);
    int i, j, k;
    unsigned short *a = (unsigned short*)malloc(size * sizeof (unsigned short));
    for (i = 0, j = mid, k = 0; k < size; k++) {
        a[k] = j == size ? array[i++]
             : i == mid ? array[j++]
             : array[j] < array[i] ? array[j++]
             : array[i++];
    }
	for (i = 0; i < size; i++) {
        array[i] = a[i];
    }
    free(a);
	}
	
unsigned long arrayListMergeSort(struct ArrayList * list) {
	clock_t begin, end;
	unsigned timp;
	begin = clock();
	mergeSortSplit(list -> array, list -> size);
	end = clock();
	timp = (end - begin) / (CLOCKS_PER_SEC / 1000);
	return timp;
}
void arrayListprint(struct ArrayList * list) {
	
	int j;
	for (j = 0; j < list -> size; j++) {
		printf("%d ", list -> array[j]);
	}
	printf("\n");
	
}
void deleteArrayList(struct ArrayList * list) {
	free(list -> array);
	list -> size = 0;
	free(list);
}