Merge Sort

• Divide and conquer
  Divider:一個序列切成兩個部分
  Conquer:各自排序
  Merge:再把兩個序列融合

• 概念
  拆成兩個n/2個序列，花O(n)排序，再merge起來

• 特性
  1.不是in-place的
  2.merge兩個序列的複雜度：O(m+n)
  3.Stable

• Merge sort tree
  

• 複雜度
  每一層複雜度皆為depth*O(n/depth) = O(n)，而深度有logn

  --> O(nlogn)