#include<stdio.h>
#include<conio.h>
#include<time.h>

int i, j, k, l, t, h, m, p, q, r, N, gora;
void mergesort(int a[]){
    gora = 1; //true
    p = 1;
    do{
        h = 1;
        m = N;
        if(gora==1){
            i = 1;
            j = N;
            k = N+1;
            l = 2*N;
        }else{
            k = 1;
            l = N;
            i = N+1;
            j = 2*N;
        }
        do{
            if(m>=p) q = p; else q = m;
            m = m-q;
            if(m>=p) r = p; else r = m;
            m = m-r;
            while(q!=0 && r!=0){
                if(a[i] < a[j]){
                    a[k] = a[i];
                    k = k+h;
                    i = i+1;
                    q = q-1;
                }else{
                    a[k] = a[j];
                    k = k+h;
                    j = j-1;
                    r = r-1;
                }
            }
            while(r!=0){
                a[k] = a[j];
                k = k+h;
                j = j-1;
                r = r-1;
            }
            while(q!=0){
                a[k] = a[i];
                k = k+h;
                i = i+1;
                q = q-1;
            }
            h = -h;
            t = k;
            k = l;
            l = t;
        }while(m!=0);
        if(gora==1) gora = 0;
        if(gora==0) gora = 1;
        p = 2*p;
    }while(p<N);
    if(gora == 0) for(i=0; i<N; i++) a[i] = a[i+N];
}

int main(){
    N=1000;
    int a[2*N];

    srand(time(NULL));
    for(i=0; i<N; i++) a[i] = rand();

    mergesort(a);

    for(i=0; i<N; i++) printf("[%d]: %d\t", i, a[i]);
    getch();
    return 0;
}