归并排序

归并排序（，或），是建立在归并操作上的一种有效的排序算法，效率為 O(n\log n) （大O符号）。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

概述
采用分治法:

• 分割：递归地把当前序列平均分割成两半。
• 整合：在保持元素顺序的同时将上一步得到的子序列整合到一起（归并）。

归并操作
归并操作（merge），也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。

递归法（Top-down）
#申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
#设定两个指针，最初位置分别为两个已经排序序列的起始位置
#比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
#重复步骤3直到某一指针到达序列尾
#将另一序列剩下的所有元素直接复制到合并序列尾

迭代法（Bottom-up）
原理如下（假设序列共有 n 个元素）：
#将序列每相邻两个数字进行归并操作，形成ceil(n/2)个序列，排序后每个序列包含两/一个元素
#若此时序列数不是1个则将上述序列再次归并，形成ceil(n/4)个序列，每个序列包含四/三个元素
#重复步骤2，直到所有元素排序完毕，即序列数为1

實作範例
C語言
迭代版：

int min(int x, int y) {
return x

遞歸版：

// 分治-治
void mergeSort_conquer(int array, int left, int mid, int right, int temp) {
// [left, mid]和[mid+1, right]两个有序数组
int i = left;
int j = mid + 1;
int index = 0;
while (i

C++
迭代版：

template // 整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(

遞歸版：

void Merge(vector &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 LeftSubArray(Array.begin() + front, Array.begin() + mid + 1);
vector RightSubArray(Array.begin() + mid + 1, Array.begin() + end + 1);
int idxLeft = 0, idxRight = 0;
LeftSubArray.insert(LeftSubArray.end(), numeric_limits::max());
RightSubArray.insert(RightSubArray.end(), numeric_limits::max());
// Pick min of LeftSubArray[idxLeft] and RightSubArray[idxRight], and put into Array[i]
for (int i = front; i &Array, int front, int end) {
if (front >= end)
return;
int mid = front + (end - front) / 2;
MergeSort(Array, front, mid);
MergeSort(Array, mid + 1, end);
Merge(Array, front, mid, end);
}

C#
public static List sort(List lst) {
if (lst.Count left = new List(); // 定义左侧List
List right = new List(); // 定义右侧List
// 以下兩個循環把 lst 分為左右兩個 List
for (int i = 0; i
/// 合併兩個已經排好序的List
///
/// 左側List

/// 右側List

///
static List merge(List left, List right) {
List temp = new List();
while (left.Count > 0 && right.Count > 0) {
if (left[0] 0) {
for (int i = 0; i 0) {
for (int i = 0; i

Ruby
def merge list
return list if list.size

Java
遞歸版：

static void merge_sort_recursive(int[] arr, int[] result, int start, int end) {
if (start >= end)
return;
int len = end - start, mid = (len >> 1) + start;
int start1 = start, end1 = mid;
int start2 = mid + 1, end2 = end;
merge_sort_recursive(arr, result, start1, end1);
merge_sort_recursive(arr, result, start2, end2);
int k = start;
while (start1
迭代版：

public static void merge_sort(int[] arr) {
int[] orderedArr = new int[arr.length];
for (int i = 2; i = arr.length ? (arr.length - 1) : (left + i / 2);
int right = i (j + 1) - 1 >= arr.length ? (arr.length - 1) : (i (j + 1) - 1);
int start = left, l = left, m = mid;
while (l

PHP
function merge_sort($arr) {
$len = count($arr);
if ($len >1) + ($len & 1);
$arr2d = array_chunk($arr, $half);
$left = merge_sort($arr2d[0]);
$right = merge_sort($arr2d[1]);
while (count($left) && count($right))
if ($left[0]

Python3
def mergeSort(nums):
if len(nums)

Erlang
%% @doc 归并排序
g_sort([]) ->
[];
g_sort([T]) ->
[T];
g_sort(L) ->
g_sort(L, length(L)).

g_sort([_, _ | _] = L, Length) ->
SplitNum = trunc(Length / 2),
{L1, L2} = lists:split(SplitNum, L),
g_merge(g_sort(L1, SplitNum), g_sort(L2, Length - SplitNum));
g_sort(L, _Length) ->
L.

%% 已经排好序的两个list合并
g_merge([], L2) ->
L2;
g_merge(L1, []) ->
L1;
g_merge([T1 | Rest1] = L1, [T2 | Rest2] = L2) ->
if
T1 = [T1 | g_merge(Rest1, L2)];
true -> [T2 | g_merge(L1, Rest2)]
end.

Javascript
递归法
function merge(left, right){
var result = [];
while(left.length > 0 && right.length > 0){
if(left[0] 迭代法

Go
package main

import (
"fmt"
"sort"
)

func MergeSort(list []int) []int {
var length = len(list)
if length

递归版

package main

import (
"fmt"
)

func merge(data []int) []int {
sum := len(data)
if sum = 2 {
left = merge(left)
}
right := data[sum/2:]
rSize := len(right)
if rSize >= 2 {
right = merge(right)
}
j := 0
t := 0
arr := make([]int, sum)
fmt.Println(left, right, data)
for i := 0; i = lSize{
arr[i] = right[t]
t++
} else if t >= rSize{
arr[i] = left[j]
j++
}
}
return arr
}

func main() {
var aa = []int{1000, 2, 31, 34, 5, 9, 7, 4, 6, 89, 90, 99, 99, 99, 99, 99}

var bb = merge(aa)
fmt.Println(bb)
}

算法复杂度
比较操作的次数介于(n\log n)/2和n\log n - n + 1。

赋值操作的次数是(2n\log n)。归并算法的空间复杂度为： \Theta(n)

参考文献
外部連結

• [http://www.nist.gov/dads/HTML/mergesort.html Dictionary of Algorithms and Data Structures: Merge sort]
• [https://www.interviewbit.com/tutorial/merge-sort-algorithm/ Merge sort Algorithm with example program]
• [https://web.archive.org/web/20000412204316/http://www.geocities.com/SiliconValley/Program/2864/File/Merge1/mergesort.html Merge Sort Algorithm Simulation]
• [http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html Mergesort For Linked Lists]
• [https://web.archive.org/web/20140407075718/http://talkera.org.cp-in-1.webhostbox.net/wp/?p=95 Mergesort in Java, Python, Perl, C, Ruby]

Sorteringsalgoritme#Flettesortering