/* array1与array2必须是连续的空间,且array1在array2之前 */
static void MERGE(void *array1, size_t nmemb1, void *array2, size_t nmemb2,
        size_t size, int (*compar)(const void *, const void*))
{
    void *i = array1, *j = array2, *k = i;
    void *end1 = array1 + nmemb1 * size;
    void *end2 = array2 + nmemb2 * size;
    void *tmp_array = NULL;
    int len;
    
    while (i < end1 && j < end2) {
        if (compar(i, j) > 0) {
            if (tmp_array == NULL) {
                len = end1 - i;
                tmp_array = malloc(len);
                memcpy(tmp_array, i, len);
                i = tmp_array;
                end1 = i + len;
            }
            memcpy(k, j, size);
            j += size;
        }
        else {
            if (tmp_array) {
                memcpy(k, i, size);
            }
            i += size;
        }
        k += size;
        if (j == end2 && tmp_array) {
            memcpy(k, i, end1 - i);
        }
    }
    if (tmp_array)
        free(tmp_array);
}
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--;
    }
}