归并排序

合併操作

合併操作（merge），也叫合併演算法，指的是將兩個已經排序的序列合併成一個序列的操作。合併排序演算法依賴合併操作。

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

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);}

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] . ' ';}

Python

# Recursively implementation of Merge Sortdef merge(left, right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    if left:
        result += left
    if right:
        result += right
    return resultdef merge_sort(L):
    if len(L) <= 1:
        # When D&C to 1 element, just return it
        return L
    mid = len(L) // 2
    left = L[:mid]
    right = L[mid:]

    left = merge_sort(left)
    right = merge_sort(right)
    # conquer sub-problem recursively
    return merge(left, right)
    # return the answer of sub-problemif __name__ == "__main__":
    test = [1, 4, 2, 3.6, -1, 0, 25, -34, 8, 9, 1, 0]
    print("original:", test)
    print("Sorted:", merge_sort(test))

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 mainimport (
"fmt")func MergeSort(array []int) []int{
n := len(array)
if n < 2 {
return array
}
key := n / 2
left := MergeSort(array[0:key])
right := MergeSort(array[key:])
return merge(left, right)}func merge(left []int, right []int) []int{
newArr := make([]int, len(left)+len(right))
i, j, index :=0,0,0
for {
if left[i] > right[j] {
newArr[index] = right[j]
index++
j++
if j == len(right) {
copy(newArr[index:], left[i:])
break
}

}else{
newArr[index] = left[i]
index++
i++
if i == len(left) {
copy(newArr[index:], right[j:])
break
}
}
}
return newArr}func main() {
array := []int{55, 94, 87, 1, 4, 32, 11, 77, 39, 42, 64, 53, 70, 12, 9}
fmt.Println(array)
array = MergeSort(array)
fmt.Println(array)}
遞迴版
package mainimport (
"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)}

演算法複雜度

比較操作的次數介於和。
賦值操作的次數是。合併演算法的空間複雜度為：