AP计算机教程11-6：归并排序

归并排序是递归的一个重要应用，不断把数组对半拆分，直到拆成单个元素。之后再将拆分的数组按正确顺序一级一级组合起来。以下演示的算法使用了大小相等的第二个数组用于按序组合拆分后的结果。之后会把所有排好序的元素覆盖到原数组上。

归并排序的算法有如下特征：

• 三个method，mergeSort、mergeSortHelper与merge
• mergeSortHelper会调用自身

以下是一个AP计算机归并排序的示例代码。

import java.util.Arrays;

public class SortTest
{
   public static void mergeSort(int[] elements)
   {
      int n = elements.length;
      int[] temp = new int[n];
      mergeSortHelper(elements, 0, n - 1, temp);
   }

   private static void mergeSortHelper(int[] elements,
                                       int from, int to, int[] temp)
   {
       if (from < to)
       {
          int middle = (from + to) / 2;
          mergeSortHelper(elements, from, middle, temp);
          mergeSortHelper(elements, middle + 1, to, temp);
          merge(elements, from, middle, to, temp);
       }
   }

   private static void merge(int[] elements, int from,
                             int mid, int to, int[] temp)
   {
      int i = from;
      int j = mid + 1;
      int k = from;

      while (i <= mid && j <= to)
      {
         if (elements[i] < elements[j])
         {
            temp[k] = elements[i];
            i++;
         }
         else
         {
            temp[k] = elements[j];
            j++;
         }
         k++;
      }

      while (i <= mid)
      {
         temp[k] = elements[i];
         i++;
         k++;
      }

      while (j <= to)
      {
         temp[k] = elements[j];
         j++;
         k++;
      }

      for (k = from; k <= to; k++)
      {
         elements[k] = temp[k];
      }
   }

   public static void main(String[] args)
   {
      int[] arr1 = {86, 3, 43};
      System.out.println(Arrays.toString(arr1));
      mergeSort(arr1);
      System.out.println(Arrays.toString(arr1));
   }
}

Under what condition will a merge sort execute faster?

Which sort should be the fastest most of the time?