算法---归并排序(Merge Sort)---多版本对比
归并排序是一种利用“分治”手段来实现的排序方法，其通过二分将数组分为若干个有序的子数组，然后再将这些子数组合并到一起组成一个新的数组。
算法的具体实现：
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++];
}
}
上述仅仅是自己在学习归并排序过程中实现的一些想法，如有不足之处还请多多指出，欢迎讨论。