#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#define CLOCKS_PER_MS 1000

void mergesort(int *values, int length);
void bubblesort(int *values, int length);
int isSorted(int *values, int length);


int main() {

    unsigned int i, j, count;

    clock_t start, end;

    int *testArray;
    for (i = 14; i < 23; i++) {

        printf("Sortiere 2^%u Felder\n", i);
        count = pow(2,i);

		testArray = (int *)malloc(sizeof(int)*count);

        for (j = 0; j<count; j++) {
            testArray[j] = rand();
        }
 
        start = clock();
        bubblesort(testArray, count);
        end = clock();
        if (isSorted(testArray, count) == 1) printf("bubble array nicht sortiert\n");
        printf("bubblesort: %li ms\n", (end-start)/CLOCKS_PER_MS);
 
        for (j = 0; j<count; j++) {
            testArray[j] = rand();
        }

        start = clock();
       mergesort(testArray, count);
        end = clock();
        if (isSorted(testArray, count) == 1) printf("merge array nicht sortiert\n");
        printf("mergesort: %li ms\n\n", (end-start)/CLOCKS_PER_MS);
 
        free(testArray);
    }
 
    return 0;
}
 
void mergesort(int *values, int length) {
    int
        left = length/2,
        right = length-left,
        i, j;
    int
        * arrLeft = (int *)malloc(sizeof(int)*left),
        * arrRight = (int *)malloc(sizeof(int)*right);
 
    if (length <= 1)
        return;
 
    //fill upper array
    for (i = 0; i < left; i++) {
        arrLeft[i] = values[i];
    }
 
    //fill lower
    for (i = 0, j = right-1; i < right; i++, j++) {
        arrRight[i] = values[j];
    }
 
    mergesort(arrLeft, left);
    mergesort(arrRight, right);
 
    for (i = 0; i < length; i++) {
        if (arrLeft[0] <= arrRight[0]) {
            values[i] = left;
        } else {
            values[i] = right;
        }
    }
 
    free(arrLeft);
    free(arrRight);
}
 
void bubblesort(int *values, int length) {
    int i, temp;
    int test = 1;
 

    while (test) {
        test=0;
        for (i = 0; i < length; i++) {
            if (values[i] > values[i+1]) {
                temp = values[i];
                values[i] = values[i+1];
                values[i+1] = temp;
                test=1;
            }
        }
        if (!test) break;
    }
}
 
int isSorted(int *values, int length) {
    int i;
    for (i = 0; i < length-1; i++) {
        if (values[i] > values[i+1])
            return 1;
    }
    return 0;
}