int i,j,k;
for(i=0,j=0,k=low; i if(L[i] > R[j])
array[k] = R[j++];
else
array[k] = L[i++];
}
while(i while(j}
void m_sort(int *array, int low, int high)
{
int center;
if(low < high) {
center = (low + high)/2;
m_sort(array, low, center);
m_sort(array, center+1, high);
merge(array, low, center, high);
}
}
int main()
{
int array[] = {23, 2, 45, 78, 1, 99, 3};
m_sort(array, 0, 6);
for(int i=0; i<=6; ++i) {
printf("%d\n", array[i]);
}
return 0;
}
时间复杂度：最坏和平均时间复杂度均为O(nlogn)
空间复杂度：上面的实现有些问题，如果真如上面实现，在函数merge中都要使用辅助函数L[m]和R[n]，那么归并了logn层，每层消耗空间O(n)，则实际消耗O(nlogn),再加上栈空间的消耗O(longn),总的消耗为O(nlogn+logn).该算法不符合空间复杂度为O(n)的要求，所以需要修改，实现如下：
#include
#include
using std::string;
void merge(int *array, int *extra, int low, int center, int high)
{
memcpy(extra+low, array+low, (high-low+1)*sizeof(int));
int i,j,k;
for(i=low,j=(center+1),k=low; i<=center && j<=high;++k) {
if(extra[i] > extra[j])
array[k] = extra[j++];
else
array[k] = extra[i++];
}
while(i<=center) array[k++] = extra[i++];
while(j<=high) array[k++] = extra[j++];
}
void m_sort(int *array, int *extra, int low, int high)
{
int center;
if(low < high) {
center = (low + high)/2;
m_sort(array, extra, low, center);
m_sort(array, extra, center+1, high);
merge(array, extra, low, center, high);
}
}
int main()
{
int array[7] = {23, 2, 45, 78, 1, 99, 3};
int extra[7];
m_sort(array, extra, 0, 6);
for(int i=0; i<=6; ++i) {
printf("%d\n", array[i]);
}
return 0;
}
空间复杂度：使用了辅助数组extra，消耗辅助空间O(n)，加上栈空间的消耗O(logn)，总的空间复杂度为
O(n+logn),如果n无限大，则空间复杂度可以简化为O(n).
递归实现归并排序的原理如下：
递归分割:
|
34 23 12 55 66 4 2 99 1 45 77 88 99 5 |
|
34 23 12 55 66 4 2 |
99 1 45 77 88 99 5 |
|
34 23 12 55 |
66 4 2 |
99 1 45 77 |
88 99 5 |
|
34 23 |
12 55 |
66 4 |
2 |
99 1 |
45 77 |
88 99 |
5 |
递归到达底部后排序返回:
|
23 34 |
12 55 |
4 66 |
2 |
1 99 |
45 77 |
88 99 |
5 |
|
12 23 34 55 |
2 4 66 |
1 45 77 99 |
88 99 5 |
|
34 23 12 55 66 4 2 |
99 1 45 77 88 99 5 |
|
1 2 4 5 12 23 34 45 55 66 77 88 99 99 |
最终实现排序
以上为归并排序的递归实现，以下将用迭代的方式实现
#include
#include
using std::string;
void merge(int *sort, int *list, int low, int center, int high)
{
int i,j,k;
for(i=low,j=(center+1),k=low; i<=center && j<=high;++k) {
if(list[i] > list[j])
sort[k] = list[j++];
else
sort[k] = list[i++];
}
while(i<=center) sort[k++] = list[i++];
while(j<=high) sort[k++] = list[j++];
}
void merge_pass(int *a, int *b, int length, int n)
{
int i;
for(i=0; i<=n-2*length; i+=2*length) {
int center = (i + i + 2*length - 1)/2;
merge(a, b, i, center, i+2*length-1);
}
if((i+length) int center = (i + i + 2*length - 1)/2;
merge(a, b, i, center, n-1);
} else {
while(i a[i] = b[i];
++i;
}
}
}
void m_sort(int *array, int n)
{
int extra[n];
int length = 1;
while(length < n) {
merge_pass(extra, array, length, n);
length *= 2;
merge_pass(array, extra, length, n);
length *= 2;
}
}
int main()
{
int data[] = {34, 23, 12, 55, 66, 4, 2, 99, 1, 45, 77, 88, 99, 5};
m_sort(data, 14);
for(int i=0; i<14; ++i) {
printf("%d ", data[i]);
}
printf("\n");
return 0;
}
时间复杂度为：O(nlogn)
空间复杂度为：这里的空间复杂度仅为所需的辅助空间，不需栈空间，为O(n)
归并排序的迭代实现的原理如下：
|
34 23 |
12 55 |
66 4 |
2 99 |
1 45 |
77 88 |
99 5 |
|
|
23 34 |
12 55 |
66 4 |
2 99 |
1 45 |
77 88 |
5 99 |
|
|
12 23 34 55 |
2 4 66 99 |
1 45 77 88 |
5 99 |
|
2 4 12 23 34 55 66 99 |
1 5 45 77 77 99 |
|
1 2 4 5 12 23 34 45 55 66 77 88 99 99 |
