【归并排序】c++实现归并排序

基本思想：归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

平均时间复杂度：

最坏时间复杂度：

最好时间复杂度：

空间复杂度：

稳定性：稳定

程序代码：

#include<iostream>
using namespace std;
 
void merge(int a[], int start, int mid, int end)
{
    int *tmp = (int *)malloc((end-start+1)*sizeof(int));
    int i = start;   
    int j = mid + 1;     
    int k = 0;    
 
    while(i <= mid && j <= end)
    {
        if (a[i] <= a[j])
            tmp[k++] = a[i++];
        else
            tmp[k++] = a[j++];
    }
 
    while(i <= mid)
        tmp[k++] = a[i++];
 
    while(j <= end)
        tmp[k++] = a[j++];
 
    for (i = 0; i < k; i++)
        a[start + i] = tmp[i];
 
    free(tmp);
};
void mergeSort(int a[], int start, int end)
{
    if(a==NULL || start >= end)
        return ;
 
    int mid = (end + start)/2;
 
    mergeSort(a, start, mid); 
    mergeSort(a, mid+1, end); 
 
    merge(a, start, mid, end);
};
int main()
{
	int a[13] = {7,1,3,6,8,2,4,9,5,0,10,12,11};
	mergeSort(a,0,12);
	for(int i = 0 ; i < 13 ; i++)
	{
	   cout<<a[i]<< ;
	}
	system("pause");
}