归并排序是一种效率很高的排序算法，其时间复杂度为θ（nlgn),下面是我学习这一算法的理解。 归并排序运用了分治策略，即把原问题分解成若干类似原问题的子问题，然后对这些子问题进行再分解，直到子问题容易求得解为止，最后将所有子问题的解合并起来构成原问题的解。 对于归并排序来说就是将原来要排序的序列A[n]（假设该序列用含有n个元素的数组表示）分解成两个子数组，然后对这两个子数组递归求解，最后原数组被分解成n个只有一个元素的子数组，所以每个子数组都已排好序，然后合并这些子数组，最后得到排好序的数组A'[n];比如对数组A[n] = {5,2,4,7,1,3,2,6}使用归并排序使它升序排序的具体过程：
下面输入一个整数N，表示要排序的元素个数，随后给出N个要排序的数，对这些数运用归并排序。
代码如下：
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#define MAX INT_MAX
/* 合并两有序数组a[p...q]和a[q+1...r] */
void MERGE(int a[], int p, int q, int r)
{
int n1 = q-p+1;
int n2 = r-q;
int i, j, k, L[n1+1], R[n2+1];
for( i=0; i<n1; i++)
L[i] = a[p+i];
for(j=0; j<n2; j++)
R[j] = a[q+j+1];
L[n1] = R[n2] = MAX;
i = j = 0;
for(k=p; k<=r; k++)
{
if(L[i]<=R[j])
{
a[k] = L[i];
i = i+1;
}
else
{
a[k] = R[j];
j = j+1;
}
}
}
/* 归并排序 */
void MERGE_SORT(int a[], int p, int r)
{
if(p<r)
{
int q = (p+r)/2;
MERGE_SORT(a,p,q);
MERGE_SORT(a,q+1,r);
MERGE(a,p,q,r);
}
}
int main()
{
int N, i;
scanf("%d",&N);
int a[N];
for(i=0; i<N; i++)
scanf("%d",&a[i]);
MERGE_SORT(a,0,N-1);
for( i=0; i<N; i++)
printf("%d ",a[i]);
return 0;
}
运行结果：
现在求其时间复杂度：
实现MERGE需要θ(n)的时间，设归并排序ｎ个元素的时间需要T(n)，那么易得T(n) = 2T(n/2)+θ(n)(当n>1时)，当n = 1时T(n) = θ(1),
使用数学归纳法易得T(n) = nlgn;