Метод слияния в алгоритме MergeSort

Question

Я видел много реализаций mergesort. Вот версия Роберта Лафора из «Структуры данных и алгоритмы на Java» (2-е издание):

private void recMergeSort(long[] workSpace, int lowerBound,int upperBound)
  {
  if(lowerBound == upperBound)            // if range is 1,
     return;                              // no use sorting
  else
     {                                    // find midpoint
     int mid = (lowerBound+upperBound) / 2;
                                          // sort low half
     recMergeSort(workSpace, lowerBound, mid);
                                          // sort high half
     recMergeSort(workSpace, mid+1, upperBound);
                                          // merge them
     merge(workSpace, lowerBound, mid+1, upperBound);
     }  // end else
  }  // end recMergeSort()


  private void merge(long[] workSpace, int lowPtr,
                           int highPtr, int upperBound)
      {
      int j = 0;                             // workspace index
      int lowerBound = lowPtr;
      int mid = highPtr-1;
      int n = upperBound-lowerBound+1;       // # of items

      while(lowPtr <= mid && highPtr <= upperBound)
         if( theArray[lowPtr] < theArray[highPtr] )
            workSpace[j++] = theArray[lowPtr++];
         else
            workSpace[j++] = theArray[highPtr++];

      while(lowPtr <= mid)
         workSpace[j++] = theArray[lowPtr++];

      while(highPtr <= upperBound)
         workSpace[j++] = theArray[highPtr++];

      for(j=0; j<n; j++)
         theArray[lowerBound+j] = workSpace[j];
      }  // end merge()

Одна интересная особенность метода слияния состоит в том, что почти все реализации не передали параметр mid методу слияния. mid рассчитывается при слиянии. Это странно, поскольку highPtr присваивается mid + 1 из вызывающего метода.

Почему автор не передал mid для слияния как merge(workSpace, lowerBound,mid, mid+1, upperBound);? Если мы напишем это так, мы легко увидим, что [lowerBound, mid] - нижний диапазон, [mid + 1, upperBound] - верхний диапазон. Я думаю, что должна быть причина, иначе я не могу понять, почему все реализации алгоритма старше полувека совпадают в такой маленькой детали.

Answer 1

В основном мы говорим о двух соседних интервалах [a..b-1] и [b..n] (границы включены), и вы спрашиваете, почему он представлен как (a, b, n) вместо (a, b-1, b, n)?

Вы сами сказали: это "такая маленькая деталь".

Это не влияет на корректность, и любая производительность, полученная при не пересчете b-1, может быть компенсирована стоимостью передачи его в качестве дополнительного параметра. Стоит ли усилий по профилированию расследовать так или иначе? Нет. Это не влияет на асимптотику алгоритма, и любая разница в производительности незначительна; о таких мелочах не стоит суетиться.

Кстати, стоит отметить, что способ вычисления среднего числа из двух чисел, как указано выше, теперь считается неработоспособным (см .: Блог Google Research: дополнительная информация, дополнительная информация - прочитать все об этом: почти все двоичные запросы и Сломаны слияния ). Джош Блох рекомендует:

int mid = (low + high) >>> 1;

---

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

Функцию, которая принимает 10 параметров, 5 из которых являются производными, анализировать гораздо сложнее, чем функцию, которая просто занимает 5. Конечно, если производные параметры дороги и / или нетривиальны для вычисления, и вы уже вычислили их значения перед вызовом функции, затем вы можете рассмотреть возможность их передачи.

На самом деле, в примере сортировки слиянием достаточно (a, n), поскольку b выводится из обоих. Однако это вычисление не является тривиальным (ошибка, которую Блох упоминает, избегает обнаружения на 2 десятилетия), поэтому было решено просто пропустить его.

b-1, напротив, слишком тривиален и лучше его опускать.

Answer 2

Если я не прочитал это, lowPtr в merge() будет изначально lowerBound из recMergeSort(), так что все в порядке: lowPtr - начало первой половины, которая будет объединена, highPtr это начало второй половины, которая будет объединена. Эти указатели продвигаются по мере слияния.

Что касается того, почему mid не было передано merge(), это выбор, и не единственный способ сделать это. То, что вы предложили, также будет работать. Возможно, для обеспечения того, чтобы mid всегда изначально был на единицу меньше highPtr в пределах merge(), хотя автора не очень беспокоит проверка входных данных (например, нижняя граница находится ниже верхней границы). Конечно, поскольку merge() является закрытым и, следовательно, вызывается только из "доверенного" кода, проверка не требуется .

Answer 3

Передача mid (или n) в качестве аргументов спасла бы некоторые тривиальные вычисления, но также предположила бы, что эти значения каким-то образом интересно отличаются от других аргументов.1006 * и upperBound (или любой эквивалентный набор, такой как lowPtr, mid и n) передает минимальный объем необходимой информации в метод слияния.

Таким образом, стилистический выборздесь нужно передавать минимальную информацию, а не исключать (тривиальные) избыточные вычисления.В практической реализации вы могли бы сделать другой выбор.(Или, в идеале, вы бы позволили вашему профилировщику сказать вам, что лучше.)