# 算法之合龙排序算法（merge sort）

www.MyException.Cn  网友分享于：2013-11-09  浏览：2次

# 归并排序算法

### 1.算法原理

• Divide：把n个元素的序列分为两个元素个数为n/2的子序列。
• Conquer：递归的调用归并排序算法对两个子序列进行排序
• Combine：对排好序的子序列进行合并，得到最后排序的结果。

归并算法用示意图表示如下：

归并排序算法的伪代码如下：

```MERGE_SORT(A, p, r)
if p < r
q = (p + r) / 2
MERGE_SORT(A, p, q)
MERGE_SORT(A, q + 1, r)
MERGE(A, p, q, r)```

两个子序列的合并（MERGE）过程如下列示意图所示：

其中合并（MERGE）的伪代码如下：

```MERGE(A, p, q, r)
n1 = q - p + 1
n2 = r - q
Let L[0.. n1] and R[0..n2] be new arrays
for i = 0 to n1 - 1
L[i] = A[p + i]
for j = 0 to n2 - 1
R[j] = A[q + j]

i = j = 0;
for k = p to r
if L[i] <= R[j]
A[k] = L[i]
i = i + 1
else
A[k] = R[j]
j = j + 1```

### 2.算法源代码实现

归并算法的C++代码实现如下

```#include <iostream>
using namespace std;

//将有二个有序数列a[first...mid]和a[mid...last]合并。
void __merge(int a[], int first, int mid, int last, int temp[])
{
int i = first, j = mid + 1;
int m = mid,   n = last;
int k = 0;

while (i <= m && j <= n)
{
if (a[i] <= a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}

while (i <= m)
temp[k++] = a[i++];

while (j <= n)
temp[k++] = a[j++];

for (i = 0; i < k; i++)
a[first + i] = temp[i];
}

void __merge_sort(int a[], int first, int last, int temp[])
{
if(first < last)
{
int mid = (first + last) / 2;
__merge_sort(a, first, mid, temp);
__merge_sort(a, mid + 1, last, temp);
__merge(a, first, mid, last, temp);
}
}
bool MergeSort(int a[], int n)
{
int *p = new int[n];
if(p == NULL)
{
return false;
}
else
{
__merge_sort(a, 0, n - 1, p);
delete[] p;
return true;
}
}

int main()
{
const int LEN = 10;

int a[LEN] = {23, 40, 45, 19, 12, 16, 90, 39, 87, 71};

cout << "Before the merge sort, the Array is:" << endl;
for(int i = 0; i < LEN; ++i)
{
cout << "a[ " << i + 1 << " ] is: "<< a[i] << endl;
}
cout << endl;

MergeSort(a, LEN);
cout << "After the merge sort, the Array is:" << endl;
for(int i = 0; i < LEN; ++i)
{
cout << "a[ " << i + 1 << " ] is: "<< a[i] << endl;
}

return 0;
}
```

### 3.算法复杂度

该算法的时间复杂度为O(nlogn)

### 4.内容来源

• 教材：Introduction to Algorithm 3rd Edition
• 白话经典算法系列之五 归并排序的实现
```
链接：白话经典算法系列之五 归并排序的实现

```