归并排序 - 维基百科，自由的百科全书

归并排序
	使用合併排序為一列數字進行排序的過程
概况
類別	排序算法
資料結構	数组
复杂度
平均時間複雜度
最坏时间复杂度
最优时间复杂度
空間複雜度
最佳解	有时是
相关变量的定义

归并排序（英語：Merge sort，或mergesort），是建立在归并操作上的一种有效的排序算法，效率為 $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 < y ? x : y; } void merge_sort(int arr[], int len) {     int *a = arr;     int *b = (int *) malloc(len * sizeof(int));     int seg, start;     for (seg = 1; seg < len; seg += seg) {         for (start = 0; start < len; start += seg * 2) {             int low = start, mid = min(start + seg, len), high = min(start + seg * 2, 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++];         }         int *temp = a;         a = b;         b = temp;     }     if (a != arr) {         int i;         for (i = 0; i < len; i++)             b[i] = a[i];         b = a;     }     free(b); }

遞歸版：

// 分治-治 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 <= mid && j <= right) {         if (array[i] < array[j]) {             temp[index++] = array[i++];         } else {             temp[index++] = array[j++];         }     }     // 剩余元素直接放入temp     while (i <= mid) {         temp[index++] = array[i++];     }     while (j <= right) {         temp[index++] = array[j++];     }     // 放回原数组     index = 0;     while (left <= right) {         array[left++] = temp[index++];     } }  // 分治-分 void mergeSort_divide(int* array, int left, int right, int* temp) {     if (left < right) {         int mid = left + (right - left) / 2;         // 左边归并排序         mergeSort_divide(array, left, mid, temp);         // 右边归并排序         mergeSort_divide(array, mid + 1, right, temp);         // 合并两个有序序列         mergeSort_conquer(array, left, mid, right, temp);     } }  void mergeSort(int* array, int size) {     int* temp = (int*)malloc(sizeof(int) * size);     mergeSort_divide(array, 0, size - 1, temp); }

C++

迭代版：

template<typename T> // 整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)的運算子功能 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; }

遞歸版：

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 - front) / 2;     MergeSort(Array, front, mid);     MergeSort(Array, mid + 1, end);     Merge(Array, front, mid, end); }

^[1]

C#

public static List<int> sort(List<int> lst) {     if (lst.Count <= 1)         return lst;     int mid = lst.Count / 2;     List<int> left = new List<int>();  // 定义左侧List     List<int> right = new List<int>(); // 定义右侧List     // 以下兩個循環把 lst 分為左右兩個 List     for (int i = 0; i < mid; i++)         left.Add(lst[i]);     for (int j = mid; j < lst.Count; j++)         right.Add(lst[j]);     left = sort(left);     right = sort(right);     return merge(left, right); } /// <summary> /// 合併兩個已經排好序的List /// </summary> /// <param name="left">左側List</param> /// <param name="right">右側List</param> /// <returns></returns> static List<int> merge(List<int> left, List<int> right) {     List<int> temp = new List<int>();     while (left.Count > 0 && right.Count > 0) {         if (left[0] <= right[0]) {             temp.Add(left[0]);             left.RemoveAt(0);         } else {             temp.Add(right[0]);             right.RemoveAt(0);         }     }     if (left.Count > 0) {         for (int i = 0; i < left.Count; i++)             temp.Add(left[i]);     }     if (right.Count > 0) {         for (int i = 0; i < right.Count; i++)             temp.Add(right[i]);     }     return temp; }

Ruby

def merge list   return list if list.size < 2    pivot = list.size / 2    # Merge   lambda { |left, right|     final = []     until left.empty? or right.empty?       final << if left.first < right.first; left.shift else right.shift end     end     final + left + right   }.call merge(list[0...pivot]), merge(list[pivot..-1]) end

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 <= end1 && start2 <= end2) 		result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++]; 	while (start1 <= end1) 		result[k++] = arr[start1++]; 	while (start2 <= end2) 		result[k++] = arr[start2++]; 	for (k = start; k <= end; k++) 		arr[k] = result[k]; } public static void merge_sort(int[] arr) { 	int len = arr.length; 	int[] result = new int[len]; 	merge_sort_recursive(arr, result, 0, len - 1); }

迭代版：

public static void merge_sort(int[] arr) { 	int[] orderedArr = new int[arr.length]; 	for (int i = 2; i < arr.length * 2; i *= 2) { 		for (int j = 0; j < (arr.length + i - 1) / i; j++) { 			int left = i * j; 			int mid = left + i / 2 >= 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 < mid && m <= right) { 				if (arr[l] < arr[m]) { 					orderedArr[start++] = arr[l++]; 				} else { 					orderedArr[start++] = arr[m++]; 				} 			} 			while (l < mid) 				orderedArr[start++] = arr[l++]; 			while (m <= right) 				orderedArr[start++] = arr[m++]; 			System.arraycopy(orderedArr, left, arr, left, right - left + 1); 		} 	} }

PHP

function merge_sort($arr) { 	$len = count($arr); 	if ($len <= 1) 		return $arr; 	$half = ($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] < $right[0]) 			$reg[] = array_shift($left); 		else 			$reg[] = array_shift($right); 	return array_merge($reg, $left, $right); }  $arr = array(21, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70); $arr = merge_sort($arr); for ($i = 0; $i < count($arr); $i++) { 	echo $arr[$i] . ' '; }

Python3

def mergeSort(nums):     if len(nums) < 2:         return nums     mid = len(nums) // 2     left = mergeSort(nums[:mid])     right = mergeSort(nums[mid:])      i = j = 0     result = []     while i < len(left) and j < len(right):         if left[i] < right[j]:              result.append(left[i])             i += 1         else:              result.append(right[j])             j += 1      while i < len(left):          result.append(left[i])          i += 1      while j < len(right):          result.append(right[j])          j += 1      return result   if __name__ == "__main__":     nums = [1, 4, 2, 3.6, -1, 0, 25, -34, 8, 9, 1, 0]     print("original:", nums)     print("Sorted:", mergeSort(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 =< T2 -> [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] < right[0]){       result.push(left.shift());     }else{       result.push(right.shift());     }   }   return result.concat(left, right); }  function mergeSort(arr){   if(arr.length <=1) return arr;   var middle = Math.floor(arr.length / 2);   var left = arr.slice(0, middle);   var right = arr.slice(middle);   return merge(mergeSort(left), mergeSort(right)); }

迭代法

Go

package main  import ( 	"fmt" 	"sort" )  func MergeSort(list []int) []int { 	var length = len(list) 	if length < 2 { 		return list 	} 	var mid = length / 2 	return merge(MergeSort(list[:mid]), MergeSort(list[mid:])) }  func merge(x, y []int) []int { 	var r []int = make([]int, len(x)+len(y)) 	for i, j := 0, 0; ; { 		if i < len(x) && (j == len(y) || x[i] < y[j]) { 			r[i+j] = x[i] 			i++ 		} else if j < len(y) { 			r[i+j] = y[j] 			j++ 		} else { 			break 		} 	} 	return r }  func main() { 	var list []int = []int{56, 48, 58, 94, 87, 4, 5, 61, 5, 8, 74, 9, 84, 15, 94, 9, 4, 31, 41, 68, 7, 4, 6, 94, 16, 9, 8, 4} 	fmt.Println(MergeSort(list)) 	fmt.Println(list)  	sort.Ints(list) 	fmt.Println(list) }

递归版

package main  import ( 	"fmt" )  func merge(data []int) []int { 	sum := len(data) 	if sum <= 1 { 		return data 	} 	left := data[0 : sum/2] 	lSize := len(left) 	if lSize >= 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 < sum; i++ { 		if j < lSize && t < rSize { 			if left[j] <= right[t] { 				arr[i] = left[j] 				j++ 			} else { 				arr[i] = right[t] 				t++ 			}	 		}  else if j >= 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)$

参考文献

^ Cormen, Thomas H. （英语：Thomas H. Cormen）; Leiserson, Charles E. （英语：Charles E. Leiserson）; Rivest, Ronald L.; Stein, Clifford. Section 2.3: Designing algorithms. Introduction to Algorithms 3rd. MIT Press and McGraw-Hill. 2009: 29–34 [1990]. ISBN 0-262-03384-4. .

外部連結

Dictionary of Algorithms and Data Structures: Merge sort （页面存档备份，存于互联网档案馆）
Merge sort Algorithm with example program （页面存档备份，存于互联网档案馆）
Merge Sort Algorithm Simulation
Mergesort For Linked Lists （页面存档备份，存于互联网档案馆）
Mergesort in Java, Python, Perl, C, Ruby

[1] Cormen, Thomas H. （英语：Thomas H. Cormen）; Leiserson, Charles E. （英语：Charles E. Leiserson）; Rivest, Ronald L.; Stein, Clifford. Section 2.3: Designing algorithms. Introduction to Algorithms 3rd. MIT Press and McGraw-Hill. 2009: 29–34 [1990]. ISBN 0-262-03384-4. .

[1]