归并算法（MERGE-SORT）（设按升序排列）

1、分冶法---分冶思想的介绍

将原始问题分解为几个规模较小但类似于原问题容易解决的子问题，递归地求解这些子问题，然后再合并子问题的解来建立原始问题的解。

分冶法在递归时的步骤

• 分解： 原问题分解为子问题，子问题是原问题规模较小的实例。
• 解决： 递归地解决子问题，若子问题足够小，则直接求解。
• 合并： 合并子问题的解。得到原问题解。

在归并排序中的体现

• 分解： 分解待排序的n个元素的序列成各自具有n/2个元素的两个子序列。
• 解决： 使用归并排序递归地排序两个子序列。
• 合并： 合并两个已排序的子序列一产生最终已排序的序列。

2、 归并排序伪代码描述

• 主过程： MERGE-SORT(A, startIndex, endIndex), A: 待排数组 startIndex： 起始数组下标 endIndex： 截止数组下标

  MERGE-SORT(A, startIndex, endIndex)
  
      if startIndex < endIndex
          midIndex = (startIndex + endIndex)/2  // midIndex取(startIndex + endIndex)/2值的底;
          MERGE-SORT(A, startIndex ,midIndex)
          MERGE-SORT(A, midIndex + 1,endIndex)
          MERGE(A, startIndex, midIndex, endIndex)

• 子过程： MERGE(A, startIndex, midIndex, endIndex)

  MERGE(A, startIndex, midIndex, endIndex)
      n1 = midindex - startIndex + 1
      n2 = endIndex - midIndex
      let L[1..n1+1] and R[1..n2+1] be new arrays
      
      for i = 1 to n1
          L[i] = A[startIndex + i -1]
          
      for j = 1 to n2
          R[j] = A[midIndex + j]
          
      L[n1+1] = Infinity
      R[n2+1] = Infinity
      i = 1
      j = 1
      
      for k = startIndex to endIndex
          if L[i] <= R[j]
              A[k] = L[i]
              i = i + 1
          else A[k] = R[j]
              j = j + 1

C#代码

static void Merge<T>(T[] arr, int left, int middle, int right) where T: IComparable<T>
{
    T[] leftArray = new T[middle - left + 1];
    T[] rightArray = new T[right - middle];

    Array.Copy(arr, left, leftArray, 0, middle - left + 1);
    Array.Copy(arr, middle + 1, rightArray, 0, right - middle);

    int i = 0;
    int j = 0;
    for (int k = left; k < right + 1; k++)
    {
        if (i == leftArray.Length)
        {
            arr[k] = rightArray[j];
            j++;
        }
        else if (j == rightArray.Length)
        {
            arr[k] = leftArray[i];
            i++;
        }
        else if (leftArray[i].CompareTo(rightArray[j]) <= 0)
        {
            arr[k] = leftArray[i];
            i++;
        }
        else
        {
            arr[k] = rightArray[j];
            j++;
        }
    }
}
static void MergeSort<T>(T[] arr, int left, int high) where T: IComparable<T>
{
    if (left< high)
    {
        int mid = (left + high) / 2;
        MergeSort(arr, left, mid);
        MergeSort(arr, mid + 1, high);
        Merge(arr, left, mid, high);
    }
}