前段时间写的，一直贴在我的博客上
复制内容到剪贴板
代码:
/* 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--;
}
}采用从树叶到树根的自底向上的方法实现。
