没有数组的递归归并排序

Question

这是我现在正在处理的问题，不知道如何解决。我应该将伪代码写入合并函数，但我不确定我应该做什么。我得到的信息如下：

Begin MergeSort(L[], start, stop)
   if (stop<=start) return;
   int m = (start+stop)/2;
   MergeSort(L, start, m);
   Mergesort(L, m+1, stop);
   merge(L, start, m, stop);
End MergeSort

我唯一被告知的另一件事是我应该找到 "merge(L, start, m, stop);" 行。我整天都在研究，我发现的一切都表明你应该有 2 个数组，分别称为左数组和右数组，用于分配递归行，使得：

Begin MergeSort(L[], start, stop)
   if (stop<=start) return;
   array left[];
   array right[];
   int m = (start+stop)/2;
   left=MergeSort(L, start, m);
   right=Mergesort(L, m+1, stop);
   merge(L, start, m, stop);
End MergeSort

如果给我这个问题，我就能解决它，但我卡住了，因为一旦我将每个子列表分解成单个元素，我什至不确定我应该调用什么他们，所以我不确定如何与他们合作。

在代码方面我仍然是初学者（掌握 C 和 Python 的基础知识），所以请尽可能简单地回答。

非常感谢您阅读本文，我希望我能得到一个答案，以便我明白我在做什么。

Answer 1

MergeSort 由 2 个函数组成：mergeSort 和 merge。第一个你已经写对了。所以，你唯一的问题是合并功能。由于归并排序不是in-space排序算法，它需要额外的space来存储数据。 Bellow 是一个非常简化的合并函数版本，它创建了额外的数组 stop - start:

Begin merge(L[] array, int start, int m, int stop) 
    if (start == stop) {
        return;
    }
    int leftPos = start;
    int rightPos = m + 1;

    int curPos = start;

    L[] temp = new L[stop - start];

    while(leftPos <= m && rightPos <= stop) {
        if (array[leftPos] <= array[rightPos]) {
            temp[curPos++] = array[leftPos++];
        } else {
            temp[curPos++] = array[rightPos++];
        }
    }
    while(leftPos <= m) {
        temp[curPos++] = array[leftPos++];
    }
    while(rightPos <= stop) {
        temp[curPos++] = array[rightPos++];
    }

    for (int i = start; i <= stop; i++) {
        array[i] = temp[i - start];
    }
End merge

没有数组的递归归并排序

Recursive Merge Sort Without Arrays

recursion

merge

mergesort

pseudocode