算法导论第二版，第二章，合并排序，非递归非栈原地合并的实现

采用从树叶到树根的自底向上的方法实现。

/* array1与array2必须是连续的空间,且array1在array2之前 */
/* 下面的MERGE为原地merge */
static void MERGE(void *array1, size_t nmemb1, void *array2, size_t nmemb2,
        size_t size, int (*compar)(const void *, const void *))
{
    void *fill_ptr = array1;
    void *block1_start = array1, *block1_end = array2 - size, *block2_start = NULL, *block2_end = NULL;
    void *i = array1, *j = array2, *m = j;
    void *temp = malloc(size);
    int flag = 0;

    block2_start = block2_end = NULL;
   
    for (; j < array2 + nmemb2 * size && block1_start <= block1_end; fill_ptr += size) {
        //printf("m=%d\n", *(int *)m);


        if (compar(i, j) > 0) {
            if (j != fill_ptr) {
                memcpy(temp, fill_ptr, size);
                memcpy(fill_ptr, j, size);
                memcpy(j, temp, size);
                block1_end += size;
                flag = 1;
            }
            else flag = 0;
            if (j <= block2_end && j >= block2_start && fill_ptr != j) {
                memcpy(temp, j, size);
                memcpy(j, m, size);
                memcpy(m, temp, size);
                //m += size;


                //block2_end += size;


                j -= size;
                if (block2_start)
                    block2_start -= size;
            }
            else if (j == block2_end && fill_ptr == j) {
                if (flag)
                    m -= size;
                j = m;
            }
            //else block1_end += size;


            j += size;
            if (flag)
                m += size;
            if (block2_start)
                block2_start += size;
            /*
            else if (j == block2_end && fill_ptr == j) {
                j += size;
            }
            */
            if (i == fill_ptr)
                i = m - size;
        }
        else {
            if (i != fill_ptr) {
                memcpy(temp, fill_ptr, size);
                memcpy(fill_ptr, i, size);
                memcpy(i, temp, size);
                if (i < block1_end) {
                    if (block2_start && block1_start >= block2_start) {
                        j = i;
                        i += size;
                        block2_start += size;
                        block2_end += size;
                    }
                    else {
                        memcpy(temp, i, size);
                        memcpy(i, m, size);
                        memcpy(m, temp, size);
                        block1_end += size;
                        m += size;
                        block2_end = i;
                        if (!block2_start) {
                            block2_start = i;
                            j = block2_start;
                        }
                        i += size;
                    }
                }
            }
            else i += size;
        }
        block1_start += size;
    }
    free(temp);
    if (j < array2 + nmemb2 * size && block2_start && block2_end && block2_start < block2_end) {
        MERGE(block2_start, (j - block2_start) / size, j, (block2_end - j + size) / size, size, compar);
    }
    if (block1_start < block1_end) {
        MERGE(block1_start, (i - block1_start) / size, i, (block1_end - i + size) / size, size, compar);
    }
}
/* 合并排序 */
void MERGE_SORT(void *base, size_t nmemb, size_t size,
        int (*compar)(const void *, const void *))
{
    if (nmemb <= 0)
        return;
    int depth = (int)(ceil(log2(nmemb)));
    int num1 = 1, num2 = 1, tmp, remain_num;
    int node_num = nmemb;
    int end_marge_flag, end_num;
    void *array1 = base, *array2 = base + size;
   
    remain_num = 0;
    end_num = 1;
    while (depth) {
        tmp = node_num / 2;
        end_marge_flag = !(node_num % 2);
        for (array1 = base, array2 = base + num1 * size; tmp; tmp--) {
            if (end_marge_flag) {
                if (!(tmp - 1) && end_num) {
                    num2 = end_num;
                    end_num = num1 + num2;
                }
            }
            MERGE(array1, num1, array2, num2, size, compar);
            array1 += num1 * size + num2 * size;
            array2 += num2 * size + num1 * size;
        }
        num1 <<= 1;
        num2 = num1;
        node_num = (node_num % 2) ? node_num / 2 + 1 : node_num / 2;
        depth--;
    }
}