비순환호출로 고친 머지소트

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

// stack implementation stack top is s[0]

int isempty(int s[]) {

    return (s[0]==0);

}

void push(int s[], int x) {

    s[++s[0]]=x;

}

int pop(int s[]) {

    return s[s[0]--];

}

int cut(int n) {

    int x=1;

    while(x<n) x=x+x;

    if(x>1) x=x/2;

    return x;

}

void split(int s[], int source, int length, int dest) {

    int x;

    x=cut(length);       // printf("n = %d cut = %d ", n, x);

    push(s,dest);       // destination

    push(s,length-x); // leng2

    push(s,x);           // leng1

    push(s,source);   // source

    push(s,2);            // merge

    push(s,dest);       // destination

    push(s,length-x); // leng2

    push(s,x);           // leng1

    push(s,source);   // source

    push(s,1);           // split

}

void merge(int data[], int source, int leng1, int leng2, int dest) {

    int i=0,j=0,k=0;

    while((i<leng1) && (j<leng2)) {

        if(data[source+i]<=data[source+leng1+j]) {

             data[dest+k]=data[source+i];

            ++i;++k;

        }

        else {

            data[dest+k]=data[source+leng1+j];

            ++j;++k;

        }

    }

    while(i<leng1) {

        data[dest+k++]=data[source+i++];

    }

    while(j<leng2) {

        data[dest+k++]=data[source+leng1+j++];

    }

}

void printdata(int data[], int n) {

    int i;

    for(i=0;i<n;++i) printf("%d ",data[i]); 

    printf("\n");

}    

int main() {

    int i, j, n, x;

    int action, source, dest, leng1, leng2;

    int s[1000]={0,};

    // we need twice of n to accomodate merge sort

    int data[20000];

    srand(time(NULL));

    printf("갯수입력: ");

    scanf("%d", &n);

    for(i=0;i<n;++i) {

        x=(rand() % 9999)+1;

        // to make program simple

        data[n+i]=data[i]=x;

    }

    printdata(data,n);

    split(s,n,n,0);

    while(!isempty(s)) {

        action=pop(s);

        source=pop(s);

        leng1=pop(s);

        leng2=pop(s);

        dest=pop(s);

        if(action==1) {

            if(leng1>1) {

                split(s,dest+leng1,leng2,source+leng1);

                split(s,dest,leng1,source);

            }

        }

        else {

            merge(data, source, leng1, leng2, dest);

        }

    }

    printdata(data,n);

    return 0;

}