c - 改进归并排序。改进 3).在输入和临时数组之间少使用一个副本

Question

我目前正在为我的算法类(class)做一个项目，但有点停滞不前。我们被指派通过实现特定更改来改进书中提到的归并排序。我在前 2 个更改中工作得很好，但第 3 个更改是 killer 级的。

我们正在改进的合并排序将输入数组的内容复制到临时数组中，然后将临时数组复制回输入数组。因此它递归地对输入数组进行排序，将排序后的两半放入临时数组中。然后它将临时数组中的两半合并在一起，将排序后的序列放入输入数组中。

改进是这种双重复制很浪费，可以不用。他的提示是:我们可以做到每次对 Merge 的调用只在一个方向上复制，但对 Merge 的调用会交替方向。

据推测，这是通过模糊原始数组和临时数组之间的界限来完成的。

我并不是真的在寻找代码，因为我相信我可以编写代码。我只是不知道我应该做什么。教授今天不在，所以我要等到下周再上他的课时才能问他。

有没有人做过这样的事情？或者可以为我破译并把它变成外行人的术语:P

第一个改进，只要数组变得足够小，它就会使用插入排序，这样它会从时间上受益匪浅。

第二个改进停止分配两个动态数组(已排序的两半)，而是分配 1 个大小为 n 的数组，这就是用来代替两个动态数组的。那是我做的最后一个。代码是:

//#include "InsertionSort.h"
#define INSERTION_CUTOFF 250
#include <limits.h>  // needed for INT_MAX (the sentinel)
void merge3(int* inputArray, int p, int q, int r, int* tempArray)
{
  int i,j,k;
  for (i = p; i <= r; i++)
  {
    tempArray[i] = inputArray[i];
  }
  i = p;
  j = q+1;
  k = p;
  while (i <= q && j <= r)
  {
    if (tempArray[i] <= tempArray[j])
    {
      inputArray[k++] = tempArray[i++];
    }
    else
    {
      inputArray[k++] = tempArray[j++];
    }
  }
}//merge3()

void mergeSort3Helper(int* inputArray, int p, int r, int* tempArray)
{
  if (r - p < INSERTION_CUTOFF)
  {
    insertionSort(inputArray,p,r);
    return;
  }
  int q = (p+r-1)/2;
  mergeSort3Helper(inputArray,p,q,tempArray);
  mergeSort3Helper(inputArray,q+1,r,tempArray);
  merge3(inputArray,p,q,r,tempArray);
}//mergeSort3Helper()

void mergeSort3(int* inputArray, int p, int r)
{
  if (r-p < 1)
  {
    return;
  }
  if (r - p < INSERTION_CUTOFF)
  {
    insertionSort(inputArray,p,r);
    return;
  }
  int* tempArray = malloc((r-p)+1*sizeof(int));
  tempArray[r+1] = INT_MAX;
  mergeSort3Helper(inputArray,p,r,tempArray);
//  This version of merge sort should allocate all the extra space
//  needed for merging just once, at the very beginning, instead of
//  within each call to merge3().
}//mergeSort3()    

Answer 1

算法是这样的:
A1: 7 0 2 9 5 1 4 3
A2:(未初始化)

第一步:
A1:不变
A2: 0 7 2 9 1 5 3 4

第 2 步:
A1: 0 2 7 9 1 3 4 5
A2:不变

第 3 步:
A1:不变
A2: 0 1 2 3 4 5 7 9

这涉及到您每次只复制一种方式，并遵循归并排序的步骤。正如您的教授所说，您可以通过交替哪个是哪个来模糊工作数组和排序数组之间的界限，并且只在排序后才进行复制。