#include <stdio.h>
#include <stdlib.h>
#include <time.h>
long long N;
int permutation_count;
clock_t start,end;
void mergesort(int a[],int i,int j);
void merge(int a[],int i1,int j1,int i2,int j2);

void output(int n, int a[]){
    for (int i = 0; i < n; ++i) printf("%d ", a[i]);
    printf("Permutation count = %d", permutation_count);
}

void generate(int n, int a[]){
    for (int i = 0; i < n; ++i) a[i] = rand() % 100;
    permutation_count = 0;
}

int check(int n, int a[]){
    for(int i = 1; i < n;  ++i)
    return (a[i] < a[i-1]) ? 0 : 1;
}

void clocker() {
	clock_t end = clock();
    printf("Elapsed: %lf seconds", (double)(end - start) / CLOCKS_PER_SEC);
}
void NeymanSort(int n, int a[]){

    int b[n], c[n], b_size = 0, c_size = 0;
    if (check(n, a)) return;
    for (int i = 0; i < n; ++i){
        if (b_size == 0 || b[b_size - 1] <= a[i]) {b[b_size] = a[i]; b_size++;}
        else if (c_size == 0  || c[c_size - 1] <= a[i]) {c[c_size] = a[i]; c_size++;}
        else if (b[b_size - 1] >= c[c_size - 1]) {permutation_count++; b[b_size] = a[i]; b_size++;}
        else {c[c_size] = a[i]; c_size++;}
    }

    int b_pointer = 0, c_pointer = 0;
    for (int i = 0; i < n; ++i){
        if (c_pointer == c_size || b[b_pointer] <= c[c_pointer]) {a[i] = b[b_pointer]; ++b_pointer;}
        else {a[i] = c[c_pointer]; ++c_pointer; permutation_count++;}
    }

    NeymanSort(n, a);
}
void BoseNelsonMerge(int l, int r, int step, int n, int a[]){
    if (l + r < n){
        if (step == 1){
            if (a[l] > a[l + r]){
                int tmp =  a[l];
                a[l] = a[l + r];
                a[l + r] = tmp;
                permutation_count++;
            }
        }
        else {
            step = step / 2;
            BoseNelsonMerge(l, r, step, n, a);
            if (l + r + step < n)
                BoseNelsonMerge(l + step, r, step, n, a);
            BoseNelsonMerge(l + step, r - step, step, n, a);
        }
    }
}


void BoseNelsonSort(int n, int a[]){
    int m = 1;
    while (m < n){
        int j = 0;
        while (j + m < n){
            BoseNelsonMerge(j, m, m, n, a);
            j += m + m;
        }
        m += m;
    }

}

void mergesort(int a[],int i,int j)
{
    int mid;

    if(i<j)
    {
        mid=(i+j)/2;
        mergesort(a,i,mid);
        mergesort(a,mid+1,j);
        merge(a,i,mid,mid+1,j);
    }
}

void merge(int a[],int i1,int j1,int i2,int j2)
{
    int temp[N];
    int i,j,k;
    i=i1;
    j=i2;
    k=0;

    while(i<=j1 && j<=j2)
    {
        if(a[i]<a[j]){
            temp[k++] = a[i++];
            permutation_count++;
        }
        else {
            temp[k++] = a[j++];
        }
    }

    while(i<=j1)
        temp[k++]=a[i++];

    while(j<=j2)
        temp[k++]=a[j++];

    for(i=i1,j=0;i<=j2;i++,j++)
        a[i]=temp[j];
}

int menu (int a[]) {
    int t;
    while(1){
        printf("Menu: \n");
        printf("1. Generate array \n");
        printf("2. Merge Sort\n");
        printf("3. NeymanSort\n");
        printf("4. BoseNelsonSort\n");
        printf("5. Print\n");
        printf("6. Exit\n");
        scanf("%d",&t);
        if(t==1) {
            generate(N, a);
            printf("Done!");
            printf("\nPermutation count = %d\n", permutation_count);
        }
        else if(t==2) {
        	start = clock();
            mergesort(a,0,N-1);
            printf("Sorted!\n");
            clocker();
            printf("\nPermutation count = %d\n", permutation_count);
        }
        else if(t==3) {
        	start = clock();
            NeymanSort(N,a);
            printf("Sorted!\n");
            clocker();
            printf("\nPermutation count = %d\n", permutation_count);
        }
        else if(t==4) {
        	start = clock();
            BoseNelsonSort(N, a);
            printf("Sorted!\n");
            clocker();
            printf("\nPermutation count = %d\n", permutation_count);
        }
        else if(t==5) {
            printf("Array: ");
            output(N, a);
            printf("\n");
            permutation_count = 0;
        }
        else if(t==6) {
            return 0;
        }
        else {
            printf("Please select an item from the suggested!\n");
        }
    }
}

int main(void) {
    srand(time(NULL));
    printf("Enter the value of array - ");
    scanf("%lld",&N);
    int a[N];
    menu(a);
    return 0;
}