更详细的请看这篇博文：

 

归并排序(Merge Sort)，基于分治法的排序，比较简单。

个人感觉其核心1是数组左右拆分之后类似队列的比较，核心2是利用for循环不断增加间隔数

类似两两合并之类的算法都可以参考

 

大致步骤：拆开为树结构遍历 -> 最下层为二叉树，不断向上合并 -> 左右比较，合并直到回到根

 

 

左侧集合比较通过则左侧索引前进，右侧集合比较通过则右侧索引前进

比较结果放入结果数组中

最后如果多出一个就把这一个直接加入结果数组

 

 

为了易于学习，代码直接使用了队列：

public class MergeSort{    public class Node    {        public int Num;        public Node Left;        public Node Right;        public void Init(int[] source)        {            var midInx = (int)Math.Floor(source.Length / (double)2);            if (source.Length > 1)            {                Left = new Node();                Left.Init(source.Take(midInx).ToArray());                Right = new Node();                Right.Init(source.Skip(midInx).ToArray());            }            else            {                Num = source[0];            }        }        public int[] Merge()        {            if (Left == null && Right == null)            {                return new int[] { Num };            }            else            {                var leftResult = Left.Merge();                var rightResult = Right.Merge();                return Merge(leftResult, rightResult);            }        }        int[] Merge(int[] leftArr, int[] rightArr)        {            var result = new List
      
       ();            var leftQueue = new Queue
       
        (leftArr);            var rightQueue = new Queue
        
         (rightArr);            while (leftQueue.Count > 0 && rightQueue.Count > 0)            {                var minValue = 0;                if (leftQueue.Peek() <= rightQueue.Peek())                    minValue = leftQueue.Dequeue();                else                    minValue = rightQueue.Dequeue();                result.Add(minValue);            }            result.AddRange(leftQueue);            result.AddRange(rightQueue);            return result.ToArray();        }    }    public int[] Execute(int[] sourceArr)    {        var root = new Node();        root.Init(sourceArr);        return root.Merge();    }}
        
       
      

 

使用:

static void Main(string[] args){    var mergeSort = new MergeSort();    var result = mergeSort.Execute(new int[] { 12, 4, 6, 3, 20, 7, 4 });    for (int i = 0; i < result.Length; i++)    {        Console.Write(result[i] + ",");    }    Console.Read();    //print: 3,4,4,6,7,12,20,}