归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；自下而上的迭代；
1. 算法步骤
1、申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
2、设定两个指针，最初位置分别为两个已经排序序列的起始位置；
3、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
4、重复步骤 3 直到某一指针达到序列尾；
5、将另一序列剩下的所有元素直接复制到合并序列尾。
2. 动图演示
3. 时间复杂度
归并排序比较占用内存，但却是一种效率高且稳定的算法。
改进归并排序在归并时先判断前段序列的最大值与后段序列最小值的关系再确定是否进行复制比较。如果前段序列的最大值小于等于后段序列最小值，则说明序列可以直接形成一段有序序列不需要再归并，反之则需要。所以在序列本身有序的情况下时间复杂度可以降至O(n)
TimSort可以说是归并排序的终极优化版本，主要思想就是检测序列中的天然有序子段（若检测到严格降序子段则翻转序列为升序子段）。在最好情况下无论升序还是降序都可以使时间复杂度降至为O(n)，具有很强的自适应性。
最好时间复杂度 | 最坏时间复杂度 | 平均时间复杂度 | 空间复杂度 | 稳定性 | |
传统归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | T(n) | 稳定 |
改进归并排序 | O(n) | O(nlogn) | O(nlogn) | T(n) | 稳定 |
TimSort | O(n) | O(nlogn) | O(nlogn) | T(n) | 稳定 |
4. 算法实现
归并排序C语言
#include <stdlib.h>
#include <stdio.h>
void Merge(int sourceArr[],int tempArr[], int startIndex, int midIndex, int endIndex)
{
int i = startIndex, j=midIndex+1, k = startIndex;
while(i!=midIndex+1 && j!=endIndex+1)
{
if(sourceArr[i] > sourceArr[j])
tempArr[k++] = sourceArr[j++];
else
tempArr[k++] = sourceArr[i++];
}
while(i != midIndex+1)
tempArr[k++] = sourceArr[i++];
while(j != endIndex+1)
tempArr[k++] = sourceArr[j++];
for(i=startIndex; i<=endIndex; i++)
sourceArr[i] = tempArr[i];
}
//内部使用递归
void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex)
{
int midIndex;
if(startIndex < endIndex)
{
midIndex = startIndex + (endIndex-startIndex) / 2;//避免溢出int
MergeSort(sourceArr, tempArr, startIndex, midIndex);
MergeSort(sourceArr, tempArr, midIndex+1, endIndex);
Merge(sourceArr, tempArr, startIndex, midIndex, endIndex);
}
}
int main(int argc, char * argv[])
{
int a[8] = {50, 10, 20, 30, 70, 40, 80, 60};
int i, b[8];
MergeSort(a, b, 0, 7);
for(i=0; i<8; i++)
printf("%d ", a[i]);
printf("\n");
return 0;
}
归并排序C++迭代版
template<typename T>
void merge_sort(T arr[], int len) {
T *a = arr;
T *b = new T[len];
for (int seg = 1; seg < len; seg += seg) {
for (int start = 0; start < len; start += seg + seg) {
int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
int k = low;
int start1 = low, end1 = mid;
int start2 = mid, end2 = high;
while (start1 < end1 && start2 < end2)
b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
while (start1 < end1)
b[k++] = a[start1++];
while (start2 < end2)
b[k++] = a[start2++];
}
T *temp = a;
a = b;
b = temp;
}
if (a != arr) {
for (int i = 0; i < len; i++)
b[i] = a[i];
b = a;
}
delete[] b;
}
归并排序C++递归版
void Merge(vector<int> &Array, int front, int mid, int end) {
// preconditions:
// Array[front...mid] is sorted
// Array[mid+1 ... end] is sorted
// Copy Array[front ... mid] to LeftSubArray
// Copy Array[mid+1 ... end] to RightSubArray
vector<int> LeftSubArray(Array.begin() + front, Array.begin() + mid + 1);
vector<int> RightSubArray(Array.begin() + mid + 1, Array.begin() + end + 1);
int idxLeft = 0, idxRight = 0;
LeftSubArray.insert(LeftSubArray.end(), numeric_limits<int>::max());
RightSubArray.insert(RightSubArray.end(), numeric_limits<int>::max());
// Pick min of LeftSubArray[idxLeft] and RightSubArray[idxRight], and put into Array[i]
for (int i = front; i <= end; i++) {
if (LeftSubArray[idxLeft] < RightSubArray[idxRight]) {
Array[i] = LeftSubArray[idxLeft];
idxLeft++;
} else {
Array[i] = RightSubArray[idxRight];
idxRight++;
}
}
}
void MergeSort(vector<int> &Array, int front, int end) {
if (front >= end)
return;
int mid = (front + end) / 2;
MergeSort(Array, front, mid);
MergeSort(Array, mid + 1, end);
Merge(Array, front, mid, end);
}
归并排序PHP
function msort(array &$arr, $low, $high){
if($low>=$high)
return;
$mid = floor(($low+$high)/2);
msort($arr, $low, $mid);
msort($arr, $mid+1, $high);
mmerge($arr, $low, $mid, $high);
}
function mmerge(array &$arr, $low, $mid, $high){
//复制数据备用
$aa = [];
for($k=$low; $k<=$high; $k++){
$aa[$k] = $arr[$k];
}
//合并数组
$i = $low;//左边起点
$j = $mid+1;//右边起点
for($k=$low; $k<=$high; $k++){
if($i>$mid){//左边处理完成，使用右边
$arr[$k] = $aa[$j++];
}elseif($j>$high){//右边处理完成，使用左边
$arr[$k] = $aa[$i++];
}elseif($aa[$i]>$aa[$j]){//左边比右边大，用右边
$arr[$k] = $aa[$j++];
}else{
$arr[$k] = $aa[$i++];
}
}
}
$a = [4,3,6,7,5,1,9,0,2];
msort($a, 0, count($a)-1);
print_r($a);
归并排序JAVA
package MergeSort;
public class MergeSort {
public static int[] mergeSort(int[] nums, int l, int h) {
if (l == h)
return new int[] { nums[l] };
int mid = (l + h - l) / 2;
int[] leftArr = mergeSort(nums, l, mid); //左有序数组
int[] rightArr = mergeSort(nums, mid + 1, h); //右有序数组
int[] newNum = new int[leftArr.length + rightArr.length]; //新有序数组
int m = 0, i = 0, j = 0;
while (i < leftArr.length && j < rightArr.length) {
newNum[m++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++];
}
while (i < leftArr.length)
newNum[m++] = leftArr[i++];
while (j < rightArr.length)
newNum[m++] = rightArr[j++];
return newNum;
}
public static void main(String[] args) {
int[] nums = new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 10 };
int[] newNums = mergeSort(nums, 0, nums.length - 1);
for (int x : newNums) {
System.out.println(x);
}
}
}
归并排序JavaScript
function merge(left, right){
var result=[];
while(left.length>0 && right.length>0){
if(left[0]<right[0]){
/*shift()方法用于把数组的第一个元素从其中删除，并返回第一个元素的值。*/
result.push(left.shift());
}else{
result.push(right.shift());
}
}
return result.concat(left).concat(right);
}
function mergeSort(items){
if(items.length == 1){
return items;
}
var middle = Math.floor(items.length/2),
left = items.slice(0, middle),
right = items.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
归并排序JavaScript非递归算法
function mergePass(arr = [], temp = new Array(arr.length), N = arr.length, length = 1){ // 将每个元素看作是相邻的数组长度为1。
let t; // 迭代深度。
for (t = 0; Math.pow(2,t) < N; t++, length *= 2) { // 每次跳过的长度翻倍。
const even = t%2 === 0; // 复用 arr 和 temp 来回赋值。
for (let left = 0; left < N; left += 2 * length) { // 左边数组起始位置 left 从0开始。
const middle = left + length < N ? left + length : left; // 右边数组起始位置 middle 就是left + 一个数组长度length 但是不要超过 N 。
const right = left + (2 * length) < N ? left + (2 * length) : N; // 右边界 right 就是 left + 两个数组长度。
merge(even ? arr : temp, even ? temp : arr, left, middle, right); // 合并每两个相邻的数组。
}
}
if(t % 2 === 0){
return arr;//返回arr
}
return temp; // 返回 temp 。
}
function merge(arr, temp, left, middle, right){
const leftEnd = middle - 1; // 通过右边数组的起始位置得到左边数组的结束位置。
while (left <= leftEnd && middle < right) { // 如果‘指针’没有越界。
if (arr[left] > arr[middle]) { // 如果左边数组第一个元素比右边数组第一个元素大。
temp[left + middle - leftEnd -1] = arr[middle++]; // 将右边数组最小的放入有序数组 temp（初始值为空)。
} else {
temp[left + middle - leftEnd -1] = arr[left++]; // 将左边数组最小的放入有序数组 temp（初始值为空)。
}
}
while(left > leftEnd && middle < right){ // 如果左边数组放完了，右边数组还有元素。
temp[left + middle - leftEnd -1] = arr[middle++]; // 那么依次将右边数组剩余的元素放入 temp 。
}
while(left <= leftEnd && middle >= right){ // 如果右边数组放完了，左边数组还有元素
temp[left + middle - leftEnd -1] = arr[left++]; // 那么依次将左边数组剩余的元素放入 temp 。
}
}
归并排序C#语言
public static void Sort(int[] a, int f, int e)
{
if (f < e)
{
int mid = (f + e) / 2;
Sort(a, f, mid);
Sort(a, mid + 1, e);
MergeMethid(a, f, mid, e);
}
}
private static void MergeMethid(int[] a, int f, int mid, int e)
{
int[] t = new int[e - f + 1];
int m = f, n = mid + 1, k = 0;
while(n <= e && m <= mid)
{
if (a[m] > a[n]) t[k++] = a[n++];
else t[k++] = a[m++];
}
while (n < e + 1) t[k++] = a[n++];
while (m < mid + 1) t[k++] = a[m++];
for (k = 0, m = f; m < e + 1; k++, m++) a[m] = t[k];
}
归并排序Visual Basic语言
Sub MergeSort(Array() As Integer, First As Integer, Last As Integer)
Dim mid As Integer = 0
If first<last Then
mid = (first+last)\ 2
MergeSort(Array, first, mid);
MergeSort(Array, mid+1, last);
Merge(Array, first, mid, last);
End If
End Sub
/*
以下示例代码实现了归并操作。array[]是元素序列，其中从索引p开始到q位置，按照升序排列，同时，从(q+1)到r也已经按照升序排列，merge()函数将把这两个已经排序好的子序列合并成一个排序序列。结果放到array中。
*/
/**
* 0 <= p <= q < r, subarray array[p..q] and array[q+1..r] are already sorted.
* the merge() function merges the two sub-arrays into one sorted array.
*/
void Merge(int array[], int p, int q, int r)
{
int i,k;
int begin1,end1,begin2,end2;
int* temp = (int*)malloc((r-p+1)*sizeof(int));
begin1 = p;
end1 = q;
begin2 = q+1;
end2 = r;
k = 0;
while((begin1 <= end1)&&( begin2 <= end2))
{
if(array[begin1] <= array[begin2]){
temp[k] = array[begin1];
begin1++;
}
else
{
temp[k] = array[begin2];
begin2++;
}
k++;
}
while(begin1<=end1 || begin2<=end2)
{
if(begin1<=end1)
{
temp[k++] = array[begin1++];
}
if(begin2<=end2)
{
temp[k++] = array[begin2++];
}
}
for (i = 0; i < =(r - p); i++)
array[p+i] = temp[i];
free(temp);
}
归并排序Python
def MergeSort(lists): if len(lists) <= 1: return lists num = int( len(lists) / 2 ) left = MergeSort(lists[:num]) right = MergeSort(lists[num:]) return Merge(left, right) def Merge(left,right): r, l=0, 0 result=[] while l<len(left) and r<len(right): if left[l] <= right[r]: result.append(left[l]) l += 1 else: result.append(right[r]) r += 1 result += list(left[l:]) result += list(right[r:]) return result print MergeSort([1, 2, 3, 4, 5, 6, 7, 90, 21, 23, 45])
归并排序Swift
//归并排序
func mergeSort(_ arr: inout [Int]) {
var gap = 1;
while gap < arr.count {
mergePass(&arr, gap: gap);
gap *= 2;
}
}
//分解合并序列，gap表示子序列的元素个数
func mergePass(_ arr: inout [Int], gap: Int) {
var i = 0;
let count = arr.count;
while i + 2 * gap - 1 < count {
mergeArray(&arr, low: i, mid: i + gap - 1, high: i + 2 * gap - 1);
i += 2 * gap;
}
//合并剩余的序列
if i + gap - 1 < count {
mergeArray(&arr, low: i, mid: i + gap - 1, high: count - 1);
}
}
//合并两个序列
func mergeArray(_ arr: inout [Int], low: Int, mid: Int, high: Int) {
var i = low;
var j = mid + 1;
var k = 0;
var array = Array<Int>(repeating: 0, count: high - low + 1);
while i <= mid && j <= high {
if arr[i] < arr[j] {
array[k] = arr[i];
i += 1;
k += 1;
} else {
array[k] = arr[j];
j += 1;
k += 1;
}
}
while i <= mid {
array[k] = arr[i];
i += 1;
k += 1;
}
while j <= high {
array[k] = arr[j];
j += 1;
k += 1;
}
//将排序好的序列复制回原数组
k = 0;
for i in low...high {
arr[i] = array[k];
k += 1;
}
}
var array = [2, 5, 8, 9, 10, 4, 3, 16, 1, 7, 8];
mergeSort(&array);
print(array);
归并排序Go语言
func mergeSort(r []int) []int {
length := len(r)
if length <= 1 {
return r
}
num := length / 2
left := mergeSort(r[:num])
right := mergeSort(r[num:])
return merge(left, right)
}
func merge(left, right []int) (result []int) {
l, r := 0, 0
for l < len(left) && r < len(right) {
if left[l] < right[r] {
result = append(result, left[l])
l++
} else {
result = append(result, right[r])
r++
}
}
result = append(result, left[l:]...)
result = append(result, right[r:]...)
return
}
归并排序PASCAL
program mergesort_1;
const maxn=7;
type
arr=array[1..maxn] of integer;
var
a,b,c:arr;
i:integer;
procedure merge(r:arr; l,m,n:integer; var r2:arr);
var
i,j,k,p:integer;
begin
i:=l;
j:=m+1;
k:=l-1;
while (i<=m) and (j<=n) do begin
k:=k+1;
if r[i]<=r[j] then begin
r2[k]:=r[i];
i:=i+1
end
else begin
r2[k]:=r[j];
j:=j+1;
end
end;
if i<=m then for p:=i to m do begin
k:=k+1;
r2[k]:=r[p];
end;
if j<=n then for p:=j to n do begin
k:=k+1;
r2[k]:=r[p];
end;
end;
procedure mergesort(var r,r1:arr; s,t:integer);
var
k:integer; c:arr;
begin
if s=t then r1[s]:=r[s]
else begin
k:=(s+t)div2;
mergesort(r,c,s,k);
mergesort(r,c,k+1,t);
merge(c,s,k,t,r1)
end;
end;
begin
write('Enterdata:');
for i:=1 to maxn do read(a[i]);
mergesort(a,b,1,maxn);
for i:=1 to maxn do write(b[i]:9);
writeln;
end.
//============================================
program mergesort_2;
const max=100000;
var
a,r:array[1..max] of longint;
n,i:longint;
procedure msort(s,t:longint);
var
m,i,j,k:longint;
begin
if s=t then exit;
m:=(s+t) div 2;
msort(s,m);
msort(m+1,t);
i:=s;
j:=m+1;
k:=s;
while (i<=m) and (j<=t) do begin
if a[i]<a[j] then begin
r[k]:=a[i];
inc(i);
inc(k);
end
else begin
r[k]:=a[j];
inc(j);
inc(k);
end;
end;
while i<=m do begin
r[k]:=a[i];
inc(i);
inc(k);
end;
while j<=t do begin
r[k]:=a[j];
inc(j);
inc(k);
end;
for i:=s to t do a[i]:=r[i];
end;
begin
readln(n);
for i:=1 to n do read(a[i]);
msort(1,n);
for i:=1 to n do writeln(a[i]);
end.