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在空间复杂度相对於其他演算法较高。