算法定义

合并排序是一种递归算法，思路如下：

• 如果源数组长度为 1，立即返回。
• 将源数组平分为两个新数组：Left 和 Right。
• 对 Left 执行递归排序。
• 对 Right 执行递归排序。
• 将排序后的 Left 和 Right 执行合并到原数组。

可以看出来，改算法的重点是已排序数组的合并过程。

算法举例

【5，4，3，2，1】

【5，4，3】【2，1】

【5，4】【3】【2，1】

【5】【4】【3】【2，1】

【4，5】【3】【2，1】

【3，4，5】【2，1】

【3，4，5】【2】【1】

【3，4，5】【1，2】

【1，2，3，4，5】

算法实现

1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 using System.Text; 5 using System.Threading.Tasks; 6  7 namespace DataStuctureStudy.Sorts 8 { 9     class MergeSort
     
      10         where T : IComparable
      
       11     {12         private static void Swap(T[] items, int left, int right)13         {14             if (left != right)15             {16                 var temp = items[left];17                 items[left] = items[right];18                 items[right] = temp;19             }20         }21 22         public static void Sort(T[] items)23         {24             if (items.Length < 2)25             {26                 return;27             }28 29             int leftSize = items.Length / 2;30             int rightSize = items.Length - leftSize;31 32             T[] left = new T[leftSize];33             T[] right = new T[rightSize];34 35             Array.Copy(items, 0, left, 0, leftSize);36             Array.Copy(items, leftSize, right, 0, rightSize);37 38             Sort(left);39             Sort(right);40             Merge(items, left, right);41         }42 43         private static void Merge(T[] items, T[] left, T[] right)44         {45             var leftIndex = 0;46             var rightIndex = 0;47 48             for (var i = 0; i < items.Length; i++)49             {50                 if (leftIndex >= left.Length)51                 {52                     items[i] = right[rightIndex];53                     rightIndex++;54                 }55                 else if (rightIndex >= right.Length)56                 {57                     items[i] = left[leftIndex];58                     leftIndex++;59                 }60                 else if (left[leftIndex].CompareTo(right[rightIndex]) < 0)61                 {62                     items[i] = left[leftIndex];63                     leftIndex++;64                 }65                 else66                 {67                     items[i] = right[rightIndex];68                     rightIndex++;69                 }70             }71         }72     }73 }
      
     

合并过程

已排序数组的合并过程比较有意思，分别对 Left 和 Right 维护一个从左到右的指针，分别是：leftIndex 和 RightIndex，当填充目标数组的第 i 个元素时，需要从 Left 和 Right 中找到剩余元素（指针到末尾部分的元素）的最小值，因为是已排序数组，只需比较 Left[LeftIndex] 和 Right[RightIndex] 的大小，将最小的元素填充到目标数组的第 i 个位置即可，然后相应的指针加 1。