写了一个归并排序实在看不出来哪里逻辑有问题，还请指点一下

[zeroday]

#include <stdio.h>
#include <stdlib.h>
typedef int T;


void merge(T _elem[], int lo, int mi, int hi)
{
    // lb, lc 作为待排序数组左右两块的边界哨兵
    int lb = mi - lo, lc = hi - mi;

    // 开辟一个临时的空间用于存储前半段待排序数组
    T* B = (T* )malloc(sizeof(T)*lb);
    // 将前半段待排序数组复制到临时空间 B 中
    for (int i = 0; i < lb; i++) B[i] = _elem[i];

    // 待排序数组的后半段为 C
    T* C = _elem + mi;

    // B[j]和C[k]中的小者续至A末尾
    for (int i = 0, j = 0, k = 0; j < lb || k < lc;)
    {
        if (j < lb && (lc <= k || B[j] <= C[k])) _elem[i++] = B[j++];
        if (k < lc && (lb <= j || C[k] < B[j])) _elem[i++] = C[k++];
    }
    free(B);
}

void mergeSort(T _elem[], int lo, int hi)
{
    if (hi - lo < 2) return;
    int mi = (lo + hi) >> 1;
    mergeSort(_elem, lo, mi);
    mergeSort(_elem, mi, hi);
    merge(_elem, lo, mi, hi);
}

int main()
{
    T elem[19] = {53, 130, 120, 14, 206, 31, 380, 39, 402, 146, 491, 51, 54, 59, 722, 79, 82, 186, 92};
    mergeSort(elem, 0, 19);
    for (int i = 0; i < 19; i++)
        printf("%d\t", elem[i]);
    return 0;
}

[diamrem]

for (int i = 0; i < lb; i++) B[i] = _elem[i];

每次都从_elme的第一个元素开始复制到临时数组里面？这里应该是_elem[lo +i]之类的吧

后面没看。

找个小input用gdb或者lldb之类的调调吧……

[SPACELAN]

1. mergeSort(elem, 0, 19) >> mergeSort(elem, 0, 18)， 第三个参数表示下标，不是长度。

2. mergeSort(_elem, mi, hi) >> mergeSort(_elem, mi + 1, hi)，子序列不要有重叠。

[zeroday]

@diamrem _elme[] 似乎没有问题，传入的参数 lo = 0

[zeroday]

@SPACELAN 好像不是这个问题，这里第三个参数，我作为哨兵，并且取不到这个下标。所以这个样看来

mergeSort(elem, 0, 19)
mergeSort(_elem, mi, hi) 就没错了。
因为在 mergeSort(_elem, lo, mi) 中本来就取不到 mi.

[arbipher]

稍微看了一下

首先把main函数改成：
https://gist.github.com/arbipher/181c8456b04498e9c951

跑一下，发现结果是
1 2 2

推测是merge出了问题

然后把
merge(_elem, lo, mi, hi);
注释掉，再跑一下

结果是
1 3 2

证明merge肯定有错
也就是说你的代码把merge之前的1 3 2
marge成了1 2 2

merge函数我没有仔细看，但是你最后的for循环用的是有问题的，你在循环体内修改了循环参数
(很久不写C了不知道会有什么问题)
建议你改成while循环

[zeroday]

@diamrem
@arbipher
@SPACELAN 谢谢帮助。发现两个问题。

填充临时变量 B 应该从 下标 lo + i 开始。
merge 中 for 循环 i 初始化应该为 lo.

for ( int i = lo, j = 0, k = 0; j < lb || k < lc;)