归并排序，就是利用递归先把待排序的序列分成各个子序列，知道每个自序列只有一个元素，然后在从底向上对各个子序列开始排序并merge,
就类似一颗二叉树，从2个只有一个元素的子序列排序并合并成一个有2个元素的序列，然后是排序病合并成4个元素的序列，然后是八个元素的序列。。。。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections.Generic;
namespace ConsoleApplication4
{
class Program
{
static void Main(string[] args)
{
int len=20;
int[] array = new int[len];
Random r = new Random();
for (int i = 0; i < len; i++)
{
array[i] = r.Next(0, len);
}
foreach(int j in array)
{
Console.Write(j+ " ");
}
Console.WriteLine("");
MergeSort m = new MergeSort();
m.Sort(array, 0, len - 1);
foreach (int j in array)
{
Console.Write(j + " ");
}
Console.WriteLine("");
}
public class MergeSort
{
//通过递归吧带排序的序列分成小的自序列，知道最后，然后在从底向上一层层merge排序。
public void Merge(int[] array, int low, int mid, int highIndex)
{
int lowIndex = low;
int arrayLen = highIndex - lowIndex + 1;
int[] tempArray = new int[arrayLen];
int highBeginIndex = mid + 1;
int tempArrayIndex = 0;
while (lowIndex <= mid && highBeginIndex <= highIndex)
{
if (array[lowIndex] < array[highBeginIndex])
{
tempArray[tempArrayIndex++] = array[lowIndex++];
}
else
{
tempArray[tempArrayIndex++] = array[highBeginIndex++];
}
}
while (lowIndex <= mid)
{
tempArray[tempArrayIndex++] = array[lowIndex++];
}
while (highBeginIndex <= highIndex)
{
tempArray[tempArrayIndex++] = array[highBeginIndex];
highBeginIndex++;
}
for (int j = low, index = 0; j <= highIndex; j++, index++)
{
array[j] = tempArray[index];
}
}
public void Sort(int[] array, int lowIndex, int highIndex)
{
int diff = (highIndex - lowIndex) / 2;
int mid = diff + lowIndex;
if (lowIndex < mid)
{
Sort(array, lowIndex, mid);
Sort(array, mid + 1, highIndex);
}
Merge(array, lowIndex, mid, highIndex);
}
}
}
}原文：http://fyifei0558.blog.51cto.com/7249113/1718823