为什么我的合并排序不起作用？

Question

它编译得很好，但是当它运行时，它会向列表中添加随机数，以及现有数字的重复。我有几个人来看这个，他们都不知道。

void mergeSort(int list[], int length) { 
    recMergeSort(list, 0, length - 1); 
} 

void recMergeSort(int list[], int first, int last) { 

    if (first < last) { 
     int mid = (first + last)/2; 
     recMergeSort(list, first, mid); 
     recMergeSort(list, mid + 1, last); 
     merge(list, first, last, mid); 
    } 
} 

void merge(int list[], int first, int last, int mid) { 

    int arraySize = last - first + 1; 
    int* tempList = new int[arraySize]; 
    int beginPart1 = first; 
    int endPart1 = mid; 
    int beginPart2 = mid + 1; 
    int endPart2 = last; 


    int index = beginPart1; 


    while (beginPart1 <= endPart1 && beginPart2 <= endPart2) { 
     if (list[beginPart1] < list[beginPart2]) { 
      tempList[index] = list[beginPart1]; 
      beginPart1++; 
     } 
     else { 
      tempList[index] = list[beginPart2]; 
      beginPart2++; 
     } 
     index++; 
    } 

    while (beginPart1 <= endPart1) { 
     tempList[index] = list[beginPart1]; 
     index++; 
     beginPart1++; 
    } 

    while (beginPart2 <= endPart2) { 
     tempList[index] = list[beginPart2]; 
     index++; 
     beginPart2++; 
    } 


    for (int i = first; i <= last; i++) { 
     list[i] = tempList[i - first]; 
    } 

    delete[] tempList; 
} 

Answer 1

在功能合并（），你错误地计算index变量：

假设开始= 10，中= 14，末端= 19（对于0总阵列尺寸.. 19，你的索引= 10，但tempList数组被索引为0..9（因为arraySize = last - first + 1 == 10）。

因此，你溢出tempList阵列，当你“合并”，你会得到数据损坏。

修正您的index变量为基于0（而不是基于beginPart1）。

Answer 2

如果我在C＃中运行此我得到以下行的IndexOutOfRangeException：

    tempList[index] = list[beginPart1]; 

，如果你跟踪它通过你可能流失一个缓冲区的末尾，因此某处的随机数我看。

Answer 3

我觉得问题就在这里：

int index = beginPart1; 

应该

int index = 0;