我如何实现将MergeSort的包含范围包括为排除范围？

Question

我正在尝试用Java实现MergeSort算法，以使其采用A[start..end]排序的数组。我真的很努力地实现它，以便它在合并中不包括传入的最后一个索引。因此，如果传入(list, 0, list.length / 2)，它将对数组进行排序，从0包含到list.length / 2排除。到目前为止，这是我的代码。我不断使索引超出范围错误，并且尝试跟踪代码，但始终感到困惑。

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);