[Algorithm]merge sort

merge sort의 기본 개념은 아래 그림과 같습니다.

정렬되지 않은 데이타가 들어오면 쪼갤수 없을때까지 쪼갠다음에 합치면서 정렬을 해나가는 알고리즘입니다.

대부분 예제 소스에는 재귀함수로 merge sort를 구현했는데, 재귀함수로 안해도 되지않을까.....라는 생각이 시작이었습니다.

 

쪼갤수 없을때까지 쪼개는과정이 불필요하다는 생각이 들었고, 그래서 제가 구현한 소스에는

처음부터 끝까지 돌면서 처음에는 두개씩 정렬, 그 다음에는 네개, 그 다음에는 8개.
이런식으로 정렬을 수행합니다.

 

재귀함수를 안쓰다보니 추가 메모리가 필요하네요;;(안쓰고도 가능한게 있으면 알려주세요)

아래는 구현한 소스입니다.

int merge_sort(void *data, int max, int data_size, cmp t_compare)
{
    void *p, *q, *ep, *eq;
    void *data1;
    void *maxdata;
    int i, ti, cmp;
    compare = t_compare;

    maxdata = data+(max*data_size);
    data1 = malloc(max*data_size);


    for(i = 2; i<(max<<1)||i==max; i<<=1) {
        p = data; q = data+((i>>1)*data_size);
        ti = 0;
        while(p<maxdata && q<maxdata) {
            ep = q; eq = p + (i*data_size);
            if (eq>maxdata)
                eq = maxdata;
            while(p<ep && q<eq) {
                if ((cmp = compare(p, q)) > 0) {
                    memcpy(data1+(ti*data_size), q, data_size);
                    q = q+data_size;
                }
                else if (cmp  < 0) {
                    memcpy(data1+(ti*data_size), p, data_size);
                    p = p+data_size;
                }
                else if (cmp ==0) {
                    memcpy(data1+(ti*data_size), q, data_size);
                    ti++;
                    memcpy(data1+(ti*data_size), p, data_size);
                    q = q+data_size;
                    p = p+data_size;
                }
                ti++;
            }
            if (p<ep) {
                while (p<ep) { memcpy(data1+(ti*data_size), p, data_size);
                    ti++;   p = p+data_size;
                }
            }
            else if (q<eq) {
                while (q<eq) { memcpy(data1+(ti*data_size), q, data_size);
                    ti++;   q = q+data_size;
                }
            }
            p = p + ((i>>1)*data_size);
            q = q + ((i>>1)*data_size);
        }
        for (ti = 0; ti<max; ti++) {
            memcpy(data+(ti*data_size), data1+(ti*data_size), data_size);
        }
    }
    return 1;
}