Улучшение сортировки слиянием. Улучшение 3). Используйте на одну копию меньше между входными и временными массивами

В настоящее время я работаю над проектом для своего класса алгоритмов и немного застрял. Нам было поручено улучшить сортировку слиянием, которая была в книге, путем внесения конкретных изменений. Я отлично справился с первыми двумя изменениями, но третье - убийственное.

Сортировка слиянием, которую мы улучшаем, копирует содержимое входного массива во временный массив, а затем копирует временный массив обратно во входной массив. Таким образом, он рекурсивно сортирует входной массив, помещая две отсортированные половины во временный массив.Затем он объединяет две половины временного массива вместе, помещая отсортированную последовательность во входной массив по мере ее поступления.

Усовершенствование состоит в том, что двойное копирование является расточительным, и без него можно обойтись. Он намекнул, что: мы можем сделать так, чтобы каждый вызов Merge копировал только в одном направлении, но вызовы Merge меняли направление.

Предположительно это делается путем размытия границ между исходным и временным массивами.

На самом деле я не ищу код, так как уверен, что смогу это написать. Я просто понятия не имею, что я должен делать. Профессора ушел на день, поэтому я не могу спросить его до следующей недели, когда у меня снова будет его курс.

Кто-нибудь делал что-то подобное раньше? Или можете расшифровать и выразить это в терминах непрофессионала для меня: P

Первое улучшение, просто он использует сортировку вставкой всякий раз, когда массив становится достаточно маленьким, чтобы это было очень выгодно с точки зрения времени.

Второе улучшение прекращает выделение двух динамических массивов (2 половины, которые сортируются) и вместо этого выделяет 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()