简单合并排序代码的行为很奇怪，50% 的时间都在处理相同的输入

Question

我为合并排序编写了以下简单代码：

它的行为很奇怪，因为数组：{38, 27, 43, 3, 9, 82, 10}

排序为：

{3 9 10 27 38 43 82 }

有时为：

{-1707474943 3 9 10 27 38 43 }

我尝试对此进行调试，但我无法理解这一点。为什么对于相同的输入，代码只有 50% 的时间正确工作。

我可以轻松复制粘贴合并排序代码，但我想了解为什么代码会这样。

void merge(int arr[], int st, int mid, int end)
{
    mid = (st+end)/2;     
    int len1 = mid - st + 1;
    int len2 = end - mid;

    int *first = new int[len1];
    int *second = new int[len2];

    int ind = st;
    for(int i = 0; i < len1; i++)
    {
        first[i] = arr[ind++];
    }

    ind = mid+1;
    for(int j = 0; j < len2; j++)
    {
        second[j] = arr[ind++];
    }

    int i = 0, j = 0, k = st;
    while(i < len1 && j < len2)
    {
        if(first[i] < second[j])
        {
            arr[k++] = first[i++]; 
        }
        else if(first[i] > second[j])
        {
            arr[k++] = second[j++];
        }
        else
        {
            arr[k++] = first[i++];
            arr[k++] = second[j++];
        }
    }

    while(i < len1)
    {
        arr[k++] = first[i++];
    }

    while(j < len2)
    {
        arr[k++] = second[j++];
    }

    delete[] first;
    delete[] second;
    display(arr, st, end);
}

void mergeSort(int arr[], int st, int end)
{
    if(st >= end)
    {
        return;
    }
    int mid = (st + end)/2;
    // cout << mid << " " << (st+end)/2 << endl;
    mergeSort(arr, st, mid);
    mergeSort(arr, mid+1, end); 
    merge(arr, st, mid, end);
}

void merge(int arr[], int st, int mid, int end)
{
    mid = (st+end)/2;     
    int len1 = mid - st + 1;
    int len2 = end - mid;


    int *first = new int[len1];
    int *second = new int[len2];


    int ind = st;
    for(int i = 0; i < len1; i++)
    {
        first[i] = arr[ind++];
    }


    ind = mid+1;
    for(int j = 0; j < len2; j++)
    {
        second[j] = arr[ind++];
    }


    int i = 0, j = 0, k = st;
    while(i < len1 && j < len2)
    {
        if(first[i] < second[j])
        {
            arr[k++] = first[i++]; 
        }
        else if(first[i] > second[j])
        {
            arr[k++] = second[j++];
        }
        else
        {
            arr[k++] = first[i++];
            arr[k++] = second[j++];
        }
    }


    while(i < len1)
    {
        arr[k++] = first[i++];
    }


    while(j < len2)
    {
        arr[k++] = second[j++];
    }


    delete[] first;
    delete[] second;
}


void mergeSort(int arr[], int st, int end)
{
    if(st >= end)
    {
        return;
    }
    int mid = (st + end)/2;
    mergeSort(arr, st, mid);
    mergeSort(arr, mid+1, end); 
    merge(arr, st, mid, end);
}

针对相同输入（相同数组）运行代码 10 次，得到正确答案 5 次，得到错误答案 5 次。

这是怎么发生的？

Answer 1

我将数组大小大小传递为“7”而不是“6”（0 索引），这导致了错误。

但是为什么它有 50% 的时间工作？