// Coded by ScratchyCode
// Try to compile in gcc with and without -O2 option
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void bubbleSort(int array[], int N);
void merge(int *A, int *L, int leftCount, int *R, int rightCount);
void mergeSort(int *A, int n);

int main(){
    // array1 and array2 are equal
    int array1[] = {
    1,51,18,56,156,84,89,1,156,16,
    11,1,61,561,189,894,51,561,651,8,
    48,65,165,1,81,1,91,65,18,489,
    98,7897,984,56,561,651,561,56,165,1561,
    651,4465,5648,97,4894984,48,564165,654489,8946,
    564654,654,44654,64564634,56465456,5456465,456456,545,566,654,
    7897,318,79,9879,4561,654,454,74,56,2,
    456,3,465,4,654,13,654,465,879,32,
    3969,28,82825,727,7781,111111,4561,4641,3465,13,
    156,1654,456,414,45,8,6,4564,123,56,
    456,46,156,564,4165564,65,231,123,4564,45,
    56,1,3156,4,651,16,1,65465,1,654,
    16,16,1,64,65,61,64,489813,13,4,
    4,41,64613,7967,64479,6131,0,49,1313,654,
    3569,9338,7812,489465,16468,16584,163,6513,131654,746,
    313,1,7,963,15113,11563,1713,651651,165165,461231,
    1717,17,78769,878,9,97,79874,897987,8974,17,
    797,9,494,494,144,4894,23123,4984,465,16165,
    8949,44849,4564,21,2121,4174,741,1231,2131,64,
    21313,1654561,4654013,456231,17456465,1312165,32321321,1321321,132153,12316
    };

    int array2[] = {
    1,51,18,56,156,84,89,1,156,16,
    11,1,61,561,189,894,51,561,651,8,
    48,65,165,1,81,1,91,65,18,489,
    98,7897,984,56,561,651,561,56,165,1561,
    651,4465,5648,97,4894984,48,564165,654489,8946,
    564654,654,44654,64564634,56465456,5456465,456456,545,566,654,
    7897,318,79,9879,4561,654,454,74,56,2,
    456,3,465,4,654,13,654,465,879,32,
    3969,28,82825,727,7781,111111,4561,4641,3465,13,
    156,1654,456,414,45,8,6,4564,123,56,
    456,46,156,564,4165564,65,231,123,4564,45,
    56,1,3156,4,651,16,1,65465,1,654,
    16,16,1,64,65,61,64,489813,13,4,
    4,41,64613,7967,64479,6131,0,49,1313,654,
    3569,9338,7812,489465,16468,16584,163,6513,131654,746,
    313,1,7,963,15113,11563,1713,651651,165165,461231,
    1717,17,78769,878,9,97,79874,897987,8974,17,
    797,9,494,494,144,4894,23123,4984,465,16165,
    8949,44849,4564,21,2121,4174,741,1231,2131,64,
    21313,1654561,4654013,456231,17456465,1312165,32321321,1321321,132153,12316
    };

    int dim = 200;
    double start, end, totalBubbleSort, totalMergeSort;

    start = clock();
    bubbleSort(array1,dim);
    end = clock();
    totalBubbleSort = (double)(end - start) / CLOCKS_PER_SEC;

    start = clock();
    mergeSort(array2,dim);
    end = clock();
    totalMergeSort = (double)(end - start) / CLOCKS_PER_SEC;

    printf("Dim array:\t%d\nBubble sort:\t%.10lf s\nMerge sort:\t%.10lf s\n",dim,totalBubbleSort,totalMergeSort);

    return 0;
}

void bubbleSort(int array[], int N){
    int i, j;
    int tmp;

    for(i=0; i<N; i++){
        for(j=0; j<N-i-1; j++){
            if(array[j] > array[j+1]){
                tmp = array[j];
                array[j] = array[j+1];
                array[j+1] = tmp;
			}
		}
	}

	return ;
}

void merge(int *A, int *L, int leftCount, int *R, int rightCount){
    // lefCount = number of elements in L
    // rightCount = number of elements in R.
    // i - to mark the index of left aubarray (L)
    // j - to mark the index of right sub-raay (R)
    // k - to mark the index of merged subarray (A)
    int i=0, j=0, k=0;

    while(i<leftCount && j< rightCount){
        if(L[i] < R[j])
            A[k++] = L[i++];
        else
            A[k++] = R[j++];
    }

    while(i < leftCount)
        A[k++] = L[i++];
    while(j < rightCount)
        A[k++] = R[j++];

    return ;
}

void mergeSort(int *A, int n){
    int mid, i, *L, *R;

    if(n < 2)
        return;             // base condition. If the array has less than two element, do nothing.

    mid = n/2;              // find the mid index.

    // create left and right subarrays
    // mid elements (from index 0 till mid-1) should be part of left sub-array
    // and (n-mid) elements (from mid to n-1) will be part of right sub-array
    L = (int*)malloc(mid * sizeof(int));
    R = (int*)malloc((n - mid) * sizeof(int));

	for(i=0; i<mid; i++)
	    L[i] = A[i];        // creating left subarray
	for(i=mid; i<n; i++)
	    R[i-mid] = A[i];    // creating right subarray

    mergeSort(L,mid);       // sorting the left subarray
    mergeSort(R,n-mid);     // sorting the right subarray
    merge(A,L,mid,R,n-mid); // Merging L and R into A as sorted list.

    free(L);
    free(R);
}