歸並排序是一種利用“分治”手段來實現的排序方法，其通過二分將數組分為若干個有序的子數組，然後再將這些子數組合並到一起組成一個新的數組。
歸並排序的實現 http://www.linuxidc.com/Linux/2014-09/107316.htm
直接插入排序的三種實現 http://www.linuxidc.com/Linux/2014-09/107313.htm
直接選擇排序及交換二個數據的正確實現 http://www.linuxidc.com/Linux/2014-09/107315.htm
排序總結之選擇式排序 http://www.linuxidc.com/Linux/2014-09/106564.htm
算法的具體實現：
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++];
}
}
上述僅僅是自己在學習歸並排序過程中實現的一些想法，如有不足之處還請多多指出，歡迎討論。
