Как я могу реализовать MergeSort с привязкой включительно к эксклюзиву?

Question

Я пытаюсь реализовать алгоритм MergeSort в Java, чтобы он сортировал массив из A[start..end]. Я действительно изо всех сил пытаюсь реализовать его, чтобы он не включал последний переданный индекс, в слияние. Я пытаюсь отследить свой код, но все время путаюсь.

Вот мой код:

public class MergeSort {

   public static void main(String[] args) {
      int[] list = new int[] { 3, 7, 5, 2, 9 };
      int[] result = mergeSort(list, 0, list.length);  
      System.out.print("[");
      for (int i = 0; i < result.length; i++) {
         System.out.print(" " + result[i]);
      }
      System.out.println("]");
   }

   public static int[] mergeSort(int[] list, int start, int end) {
      if (end - start < 2) {
         return list;
      } else {
         int mid = (start + end) / 2;
         mergeSort(list, start, mid);
         mergeSort(list, mid + 1, end);
         merge(list, start, mid, end);
         return list;
      }
   }

   public static void merge(int[] list, int start, int mid, int end) {
      int[] copy = new int[list.length];
      for (int i = 0; i < list.length; i++) {
         copy[i] = list[i];
      }
      int i = start;
      int k = start;
      int j = mid + 1;
      while (i <= mid && j <= end) {
         if (copy[i] <= copy[j]) {
            list[k] = copy[i];
            i++;
         } else {
            list[k] = copy[j];
            j++;
         }
         k++;
      }
      while (i <= mid) {
         list[k] = copy[i];
         i++;
         k++;
      }
      while (j < end) {
         list[k] = copy[j];
         j++;
         k++;
      } 
   }   
}

Answer 1

Вызов mergesort со срезом, определенным с включенным start и исключенным end, действительно разумный подход, так как последовательность вызова проще: merge(array, 0, array.length) и допускает пустые срезы, что необходимо для пустых массивов.

В вашем методе mergesort есть ошибка: правый срез начинается с mid и заканчивается до end, следовательно, вызов должен быть mergeSort(list, mid, end);

Есть проблемы в merge метод тоже:

• Вы не должны дублировать весь list, а только срез от start до end (исключено). Проще, если вы объединитесь во временный массив и скопируете его обратно после объединения. При таком подходе вы можете остановить слияние, когда левая часть исчерпана, поскольку оставшиеся значения из правой части уже находятся в нужном месте.
• Вы должны использовать оператор < вместо <=, когда Сравнение значений текущего индекса с верхними границами, которые исключаются с помощью этого подхода.

Вот исправленная версия:

public class MergeSort {

   public static void main(String[] args) {
      int[] list = new int[] { 3, 7, 5, 2, 9 };
      int[] result = mergeSort(list, 0, list.length);  
      System.out.print("[");
      for (int i = 0; i < result.length; i++) {
         System.out.print(" " + result[i]);
      }
      System.out.println(" ]");
   }

   public static int[] mergeSort(int[] list, int start, int end) {
      if (end - start < 2) {
         return list;
      } else {
         // compute the mid point:
         //  the left part spans from start included to mid excluded
         //  the right part spans from mid included to end excluded
         // avoid adding start and end to prevent overflow overflow for very large arrays
         int mid = start + (end - start) / 2;
         mergeSort(list, start, mid);
         mergeSort(list, mid, end);
         merge(list, start, mid, end);
         return list;
      }
   }

   public static void merge(int[] list, int start, int mid, int end) {
      int[] temp = new int[end - start];
      int k = 0;     // index into the temporary array
      int i = start; // index into the left part, stop at mid
      int j = mid;   // index into the right part, stop at end
      // select from left or right slices and store into the temp array
      while (i < mid && j < end) {
         if (list[i] <= list[j]) {
            temp[k++] = list[i++];
         } else {
            temp[k++] = list[j++];
         }
      }
      // copy the remaining elements from the left part
      while (i < mid) {
         temp[k++] = list[i++];
      }
      // copy the sorted elements back to the original list
      for (i = 0; i < k; i++) {
         list[start + i] = temp[i];
      }
   }   
}

Answer 2

Либо вызовите mergeSort(list, 0, list.length - 1);

, либо вызовите вспомогательную функцию, скажем F. Так, например, вы бы назвали F(list, 0, list.length);, где единственное, что сделал бы F, это позвонило бы mergeSort(list, 0, list.length - 1);.

Таким образом, вы даже больше не касаетесь mergeSort. Вы просто звоните F.

Редактировать:

public class MergeSort {

   public static void main(String[] args) {
      int[] list = new int[] {3, 7, 5, 2, 9};
      int[] result = mergeSort(list, 0, list.length);  
      System.out.print("[");
      for (int i = 0; i < result.length; i++) {
         System.out.print(" " + result[i]);
      }
      System.out.println("]");
   }

   public static int[] mergeSort(int[] list, int start, int end) {
      return F(list, start, end - 1);
   }

   public static int[] F(int[] list, int start, int end) {
      if (end - start < 2) {
         return list;
      } else {
         int mid = (start + end) / 2;
         F(list, start, mid);
         F(list, mid + 1, end);
         merge(list, start, mid, end);
         return list;
      }
   }

   public static void merge(int[] list, int start, int mid, int end) {
      int[] copy = new int[list.length];
      for (int i = 0; i < list.length; i++) {
      copy[i] = list[i];
      }
      int i = start;
      int k = start;
      int j = mid + 1;
      while (i <= mid && j <= end) {
         if (copy[i] <= copy[j]) {
            list[k] = copy[i];
            i++;
         } else {
            list[k] = copy[j];
            j++;
         }
         k++;
      }
      while (i <= mid) {
         list[k] = copy[i];
         i++;
         k++;
      }
      while (j < end) {
         list[k] = copy[j];
         j++;
         k++;
      } 
   }   
}