归并排序是一种利用“分治”手段来实现的排序方法，其通过二分将数组分为若干个有序的子数组，然后再将这些子数组合并到一起组成一个新的数组。

算法的具体实现：

void sort::merge_sort(int* a, const int low, const int high)
{
?if(low>= high)
? return;
?int mid = (low+high)/2;
?merge_sort(a,low,mid);
?merge_sort(a,mid+1,high);
?merge(a,low,mid,high);
}

上述实现可以看出，此算法通过递归将数组分为若干个有序的小数组，然后再使用merge方法将这些小数组进行合并，从而完成数组的排序。

merge方法的实现

void sort::merge(int*a ,const int low,const int mid, const int high)
{
?if(a[mid]<=a[mid+1])
? return ;
?int* copy_a = new int[high-low+1];
?for(int i=low; i<=high; i++)
? copy_a[i-low] = a[i];
?int i=low;
?int j=mid+1;
?for(int k=low; k<=high; k++)
?{
? if(i>mid)
? {
? ?a[k] = copy_a[j-low];
? ?j++;
? }
? else if(j>high)
? {
? ?a[k] = copy_a[i-low];
? ?i++;
? }
? else if(copy_a[i-low]>copy_a[j-low])
? {
? ?a[k] = copy_a[j-low];
? ?j++;
? }
? else
? {
? ?a[k] = copy_a[i-low];
? ?i++;
? }
?}
?delete[] copy_a;
}

上述实现可以看出，其实就是将两个有序的数组合并到一个新的数组中而已。

算法的时间复杂度分析，假设有N个数，使用归并排序所需的时间为T(N)，则从算法的实现可以看出，对N个数排序，需要先分别对左右两边的N/2个数排序，时间为2T(N/2)，然后再将排序的两个数组合并，所需时间为N，因此可得T(N) = 2*T(N/2)+N，计算可得T(N)=NlogN。

上述算法可有改进的地方。显然是有的。

首先，如果使用归并排序来排序较小的数组的话，其算法性能没有之前所说的插入排序好（插入排序算法实现），为此可以设定一个阈值，再使用归并排序的过程中如果子数组的元素个数小于这个阈值时，使用插入排序来对相应的子数组进行排序。

算法实现：

void sort::merge_sort_update1(int* a, const int low, const int high)
{
?if((high-low + 1) < N)
?{
? for(int i=low+1; i<=high; i++)
? {
? ?int j=i;
? ?int temp = a[i];
? ?for(; j>low && temp < a[j-1]; j--)
? ?{
? ? a[j] = a[j-1];
? ?}
? ?a[j] = temp;
? }
? return;
?}
?int mid = (low + high)/2;
?merge_sort_update1(a,low,mid);
?merge_sort_update1(a,mid+1,high);
?merge(a,low,mid,high);
}

上述算法改进之后性能上比原来的归并排序稍好，但是算法的时间复杂度仍然为O(NlogN)。

能否再进一步改进呢？

观察发现，归并排序始终使用一个备份数组来存储排序后的元素，然后再将排序后的元素复制到原来的数组中。在数组新建的过程中将会花费大量的时间。为此可以在这个方面改进一下。可以使用一个实现建好的数组，然后只需使用赋值运算即可，避免了不必要的数组的新建与删除，从而加快了算法的执行速度。

算法实现：

void sort::merge_sort_update2(int* a, const int low, const int high, int* copy_a)
{
?if(low>=high)
? return;
?int mid = (low+high)/2;
?merge_sort_update2(a,low,mid,copy_a);
?merge_sort_update2(a,mid+1,high,copy_a);
?merge_update2(a,low,mid,high,copy_a);
?for(int i=low; i<=high; i++)
? copy_a[i] = a[i];
}

void sort::merge_update2(int*a ,const int low,const int mid, const int high,const int * copy_a)
{
?if(a[mid] <= a[mid+1])
? return;
?int i=low;
?int j=mid+1;
?for(int k=low; k<=high; k++)
?{
? if(i>mid)
? ?a[k] = copy_a[j++];
? else if(j>high)
? ?a[k] = copy_a[i++];
? else if(copy_a[i] > copy_a[j])
? ?a[k] = copy_a[j++];
? else
? ?a[k] = copy_a[i++];
?}
}

上述仅仅是自己在学习归并排序过程中实现的一些想法，如有不足之处还请多多指出，欢迎讨论。