合并排序是遵循分而治之的方法。 考虑一下，假设有n个元素的数组A。该算法分3个步骤处理元素。
- 如果
A包含0或1个元素，则它已经被排序，否则，将A分成两个具有相同数量元素的子数组。 - 使用合并排序递归地对两个子数组进行排序。
- 组合子数组以形成单个最终排序数组，维护数组的顺序。
合并排序背后的主要思想是，短列表需要较少的时间进行排序。
复杂度
| 复杂度 | 最好情况 | 平均情况 | 最坏情况 |
|---|---|---|---|
| 时间复杂度 | O(n log n) | O(n log n) | O(n log n) |
| 空间复杂度 | - | - | O(n) |
示例：
考虑以下7个元素的数组，使用合并排序对数组进行排序。
A = {10, 5, 2, 23, 45, 21, 7}
算法
第1步 : [INITIALIZE] SET I = BEG, J = MID + 1, INDEX = 0
第2步 : 当(I <= MID) AND (J<=END)时，循环执行
IF ARR[I] < ARR[J]
SET TEMP[INDEX] = ARR[I]
SET I = I + 1
ELSE
SET TEMP[INDEX] = ARR[J]
SET J = J + 1
[IF结束]
SET INDEX = INDEX + 1
[结束循环]
第3步 : [复制右子数组的其余元素(如果有的话)]
IF I > MID
当 while J <= END时，循环
SET TEMP[INDEX] = ARR[J]
SET INDEX = INDEX + 1, SET J = J + 1
[结束循环]
[复制右子数组的其余元素(如果有的话)]
ELSE
当 while I <= MID 时，循环
SET TEMP[INDEX] = ARR[I]
SET INDEX = INDEX + 1, SET I = I + 1
[循环结束]
[IF结束]
第4步 : [将TEMP的内容复制回ARR] SET K = 0
第5步 : 当 while K < INDEX 时，循环
SET ARR[K] = TEMP[K]
SET K = K + 1
[结束循环]
第6步 : 退出
MERGE_SORT(ARR，BEG，END)
第1步：IF BEG <END
SET MID =(BEG + END)/ 2
CALL MERGE_SORT(ARR，BEG，MID)
CALL MERGE_SORT(ARR，MID + 1，END)
MERGE(ARR，BEG，MID，END)
[结束]
第2步：结束
使用C语言实现合并排序算法，代码以下所示 -
#include<stdio.h>
void mergeSort(int[],int,int);
void merge(int[],int,int,int);
void main ()
{
int a[10]= {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};
int i;
mergeSort(a,0,9);
printf("printing the sorted elements");
for(i=0;i<10;i++)
{
printf("\n%d\n",a[i]);
}
}
void mergeSort(int a[], int beg, int end)
{
int mid;
if(beg<end)
{
mid = (beg+end)/2;
mergeSort(a,beg,mid);
mergeSort(a,mid+1,end);
merge(a,beg,mid,end);
}
}
void merge(int a[], int beg, int mid, int end)
{
int i=beg,j=mid+1,k,index = beg;
int temp[10];
while(i<=mid && j<=end)
{
if(a[i]<a[j])
{
temp[index] = a[i];
i = i+1;
}
else
{
temp[index] = a[j];
j = j+1;
}
index++;
}
if(i>mid)
{
while(j<=end)
{
temp[index] = a[j];
index++;
j++;
}
}
else
{
while(i<=mid)
{
temp[index] = a[i];
index++;
i++;
}
}
k = beg;
while(k<index)
{
a[k]=temp[k];
k++;
}
}
执行上面示例代码，得到以下结果：
printing the sorted elements
7
9
10
12
23
23
34
44
78
101
使用Java语言实现合并排序算法，代码以下所示 -
public class MyMergeSort {
void merge(int arr[], int beg, int mid, int end) {
int l = mid - beg + 1;
int r = end - mid;
int LeftArray[];
int RightArray[];
LeftArray = new int[l];
RightArray = new int[r];
for (int i = 0; i < l; ++i)
LeftArray[i] = arr[beg + i];
for (int j = 0; j < r; ++j)
RightArray[j] = arr[mid + 1 + j];
int i = 0, j = 0;
int k = beg;
while (i < l && j < r) {
if (LeftArray[i] <= RightArray[j]) {
arr[k] = LeftArray[i];
i++;
} else {
arr[k] = RightArray[j];
j++;
}
k++;
}
while (i < l) {
arr[k] = LeftArray[i];
i++;
k++;
}
while (j < r) {
arr[k] = RightArray[j];
j++;
k++;
}
}
void sort(int arr[], int beg, int end) {
if (beg < end) {
int mid = (beg + end) / 2;
sort(arr, beg, mid);
sort(arr, mid + 1, end);
merge(arr, beg, mid, end);
}
}
public static void main(String args[]) {
int arr[] = { 90, 23, 101, 45, 65, 23, 67, 89, 34, 23 };
MyMergeSort ob = new MyMergeSort();
ob.sort(arr, 0, arr.length - 1);
System.out.println("\nSorted array");
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i] + "");
}
}
}
执行上面示例代码，得到以下结果：
Sorted array
23
23
23
34
45
65
67
89
90
101
使用C# 语言实现合并排序算法，代码以下所示 -
using System;
public class MyMergeSort
{
void merge(int[] arr, int beg, int mid, int end)
{
int l = mid - beg + 1;
int r = end - mid;
int i,j;
int[] LeftArray = new int [l];
int[] RightArray = new int [r];
for (i=0; i<l; ++i)
LeftArray[i] = arr[beg + i];
for (j=0; j<r; ++j)
RightArray[j] = arr[mid + 1+ j];
i = 0; j = 0;
int k = beg;
while (i < l && j < r)
{
if (LeftArray[i] <= RightArray[j])
{
arr[k] = LeftArray[i];
i++;
}
else
{
arr[k] = RightArray[j];
j++;
}
k++;
}
while (i < l)
{
arr[k] = LeftArray[i];
i++;
k++;
}
while (j < r)
{
arr[k] = RightArray[j];
j++;
k++;
}
}
void sort(int[] arr, int beg, int end)
{
if (beg < end)
{
int mid = (beg+end)/2;
sort(arr, beg, mid);
sort(arr , mid+1, end);
merge(arr, beg, mid, end);
}
}
public static void Main()
{
int[] arr = {90,23,101,45,65,23,67,89,34,23};
MyMergeSort ob = new MyMergeSort();
ob.sort(arr, 0, 9);
Console.WriteLine("\nSorted array");
for(int i =0; i<10;i++)
{
Console.WriteLine(arr[i]+"");
}
}
}
执行上面示例代码，得到以下结果：
Sorted array
23
23
23
34
45
65
67
89
90
101
