• 算法思想
  将原问题分解为几个规模较小但类似于原问题的子问题，递归的求解这些子问题，然后再合并这些子问题的解来建立原问题的解。
• 归并排序操作
  分解：将待排序的包含n个元素的序列分解为各含n/2个元素的子序列
  解决：使用归并排序递归的排序两个子序列
  合并：合并两个子序列以产生已排序的答案
• 归并排序算法时间复杂度 θ（nlgn）
• 归并排序伪代码实现
  排序子数组A[p..r]中的元素
  

• 归并排序之C#实现

  using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading.Tasks;namespace MergeSort{    class Program    {        static void Main(string[] args)        {            Random rd = new Random();            int[] data = new int[49];            for (int i = 0; i < data.Length; i++)            {                data[i] = rd.Next(100);            }            MergeSort(data, 0, data.Length-1);        }        static void MergeSort(int[] arr,int p,int r)        {            //排序子数组arr[p..r]中的元素            if (p >= r) return;            int q =(int)Math.Floor((p + r) / 2.0); //Math.Floor向下取整            MergeSort(arr, p, q);            MergeSort(arr, q + 1, r);            Merge(arr, p, q, r);        }        static void Merge(int[] arr,int p,int q,int r)        {            //假设arr[p..q]和arr[q+1,r]都已排好序            //从两个数组中取较小的元素至输出数组中，知道其中一个输入数组为空，            //然后将剩余输入数组中元素全部移到输出数组，为了避免在每一步都判断输入数组是否为空，            //在两个输入数组尾部放置一个哨兵 inf            int n1 = q - p + 1;            int n2 = r - q;            //创建左右两个新的数组            int[] LeftArr = new int[n1 + 1];            int[] RightArr = new int[n2 + 1];            for(int i=0;i