[算法]归并排序

概念

使用的思想是分治思想。把需要排序的数组中重建分成两部分，然后前后两部分分别排序，需要一直分解下去，直到能两个值相互比较。然后再将排序好的两个部分合并在一起。

合并

我们需要申请一个临时数组，这个数组的大小和我们排序的两个组的大小之和一样。然后我们用两个下标i，j，来标识我们当前读到的是两个组的第几个位置，然后这两个下标的值来做比较，但一个值满足要求的时候，我们就把这个值放在临时数组里，然后这个下标后移一位，继续比较。当任意一个下标到达那个组的最后一位的时候，我们就不需要做比较了，直接把另外一组剩下的放在临时数组的最后。

void merge_sort_c(int [] a,int p,int r)
            {
                if (p >= r)
                    return;
                int q = (p + r) / 2;
                merge_sort_c(a,p, q);
                merge_sort_c(a, q + 1, r);
                merage(a, p, q, r);
            }
            void merage(int[]a,int p,int q,int r)
            {
                int i = p;
                int j = q+1;
                int k = 0;
                int[] temp = new int[r - p+1];
                while (i <= q && j <= r)
                {
                    if (a[i] <= a[j])
                    {
                        temp[k++] = a[i++];
                    }
                    else
                    {
                        temp[k++] = a[j++];
                    }
                }
                int start = i;
                int end = q;
                if (j <= r)
                {
                    start = j;
                    end = r;
                }
                while (start <= end)
                {
                    temp[k++] = a[start++];
                }
                for(int ii = 0; ii < r - p+1; ii++)
                {
                    a[p + ii] = temp[ii];
                }
            }

1. 当我们把第二组的多出来的数据整体放在第一组后面，那归并排序是稳定排序

2. 归并排序的时间复杂度o(nlogn）

3. 归并排序的空间复杂度不是原地排序，因为在合并的时候需要临时空间。o(n)