static void Main(string[] args)
{
    //随机10W个数据
    int[] datas = new int[100000];
    Random r = new Random();
    for (int i = 0; i < 100000; i++) {
        datas[i] = r.Next(1,10000);
    }
    Stopwatch stopwatch = new Stopwatch();

    stopwatch.Start();
    sort(datas);//排序
    stopwatch.Stop();

    foreach (var data in datas) {
        Console.WriteLine(data);
    }
    Console.WriteLine();
    Console.WriteLine("用时：" + stopwatch.ElapsedMilliseconds);

    Console.ReadKey();
}

static void sort(int[] datas) {
    int length = datas.Length;
    int[] temp = new int[length];
    sort(datas, 0, length - 1, temp);
}

static void sort(int[] datas,int left,int right,int[] temp) {
    if (left < right) {
        int mid = (left + right)/2;
        //拆分
        sort(datas, left, mid, temp);
        sort(datas, mid + 1, right, temp);
        //合并，拆到不能拆就合并
        merge(datas, left, mid, right, temp);
    }
}

static void merge(int[] datas, int left, int mid, int right, int[] temp) {
    int i = left;
    int j = mid + 1;
    int t = 0;

    //对比左右两边（两边都已经是有序的了，所以从左往右对比）,排序(谁小先)填充到临时数组
    while (i <= mid && j <= right) {
        if (datas[i] < datas[j])
        {
            temp[t++] = datas[i++];
        }
        else {
            temp[t++] = datas[j++];
        }
    }

    //填充剩下了
    while (i <= mid) {
        temp[t++] = datas[i++];
    }

    while (j <= right) {
        temp[t++] = datas[j++];
    }

    //将排序好的临时数据覆盖到原来的数组中
    t = 0;
    while (left <= right) {
        datas[left++] = temp[t++];
    }
}

思想：将数据一直对半分组，分到组的数据都排序好为止(1个数据肯定是排序好的)，再将相邻的组合并起来（边合并，边排序），合并成的组又是一个排序好的组。

时间复杂度：O(nlogn)

10W个随机数据排序用时：33ms

稳定而又快速的排序方法，参考：dreamcatcher-cx（归并排序）