Divide and conquer（分而治之法）

Divide and conquer 顧名思義是一種將問題分解為小問題再依次解決，最後再將解決問題合併的方法。Divide and conquer有許多優點，在排序演算法中，Merge sort是經典的Divide and conquer，在討論優點之前，先來看下列這張圖。

圖片來源：Wiki

從上圖可以看到，要將一個無序的資料結構，排序為從大到小的array。先將array從中間切割，再將切割後的資料進行切割，直到兩兩進行比對，比對後進行由右到左，由小到大的排序，最後再將排序後的資料進行組合。

Divide and conquer優點

1. 解決不同問題
2. 更有效率的演算法（所耗費的時間複雜度為n log(n))
3. 並行性

Merge Sort（合併排序）

合併排序是將想要排序的數列分割成幾乎等長的兩個數列，直到無法再分割（也就是每個群組只剩下一個數）時，在整合（合併）各組數列。合併時是將已排序完成的兩個數列整合成一個排序完成的數列，反覆進行同樣的操作，直到全部的數形成一個數列。

import random

#從1-100中隨機讀取8個數字
nums = random.sample(range(1,100), 8)
print(nums)
tmp = [0,0,0,0,0,0,0,0]

#將資料分成兩個部分:L(left)+R(right)
def merge(L, M, R):
    #left：目前左半部執行到第幾個element，L為初始值
    left = L
    #right：目前右半部執行到第幾個element，M+1為初始值
    right = M+1
    #i：merge後暫存tmp的索引值，L為初始值
    i = L
    while (left <= M) and (right <= R):
        if nums[left]<nums[right]:
            tmp[i]=nums[left]
            left = left+1
        else:
            tmp[i]=nums[right]
            right = right+1
        i = i+1
    while left <= M:
        tmp[i] = nums[left]
        i = i+1
        left = left +1
    while right <= R:
        tmp[i]=nums[right]
        i = i + 1
        right = right +1
    for i in range(L, R+1):
        nums[i]=tmp[i]

#Recursion
def mergesort(L,R):
    if L < R:
        M = (L+R)//2
        mergesort(L, M)
        mergesort(M+1, R)
        merge(L, M, R)
        print("L=",L,"M=",M,"R=",R)
        for item in nums:
            print(item,' ',end='')

mergesort(0,7)

function merge(a1, a2) {
  let result = [];
  let i = 0;
  let j = 0;

  
  while (i < a1.length && j < a2.length) {
    if (a1[i] > a2[j]) {
      result.push(a2[j]);
      j++;
    } else {
      result.push(a1[i]);
      i++;
    }
  }

  // a1 or a2 might have some elements left
  // use loop to put them all into result

  while (i < a1.length) {
    result.push(a1[i]);
    i++;
  }
  while (j < a2.length) {
    result.push(a2[j]);
    j++;
  }

  return result;
}

function mergeSort(arr) {
  if (arr.length === 1) {
    return arr;
  } else {
    let middle = Math.floor(arr.length / 2);
    let left = arr.slice(0, middle);
    let right = arr.slice(middle, arr.length);
    return merge(mergeSort(right), mergeSort(left));
  }
}

console.log(mergeSort([15, 3, 17, 18, 35, 11, 0, 36, -336, 1054]));

結論

Merge sort沒有最差與最佳的情況，時間複雜度都是n log(n)，但使用了Recursion的方式，所以Merge sort在空間複雜度相對於其他演算法較高。