普通的歸并(merge)障涯，j將兩個有序的數(shù)列合并起來罐旗，形成一個更大的有序數(shù)列。在leetcode有這樣
? ? ? 令有序鏈表A和B唯蝶，首先比較兩個鏈表里第一個數(shù)九秀，如果A中第一個數(shù)不大于B中第一個數(shù)，那么把A中第一個數(shù)放入到C(新鏈表),并把A中第一個數(shù)刪除粘我。如果B第一個數(shù)更小鼓蜒，則反痹换。
以此類推，直至A和B中的數(shù)都被取盡都弹。如果中間娇豫，A或者B先被取盡，后面未取的一部分可以直接放入C
假如畅厢，A和B不一定是有序的冯痢，那又該怎么辦呢。如果鏈表很小框杜，比如說只有一個元素(數(shù)字）浦楣，那么再一個一個排序不就行了。
在歸并排序中引入 分治(divide and conquer)霸琴。分治椒振，就是將復雜的問題，分解成兩個甚至多個規(guī)模相同甚至類似的問題梧乘，再對子問題細分澎迎，直至子問題變得十分簡單。
歸并排序使用了分治的思想选调，而其實現(xiàn)的過程卻是使用遞歸來實現(xiàn)的夹供。
? ? ? ? 這個只是最經(jīng)典的2路歸并算法，如果將數(shù)組分為更多組(假設K組),是k路歸并算法仁堪。盡管可通過遞歸樹T(n)=kT(n/3)+O(n)來計算其時間復雜度哮洽，時間復雜度看起來會少，實際上花費的時間會更多弦聂，因為合并功能花費的時間會變得更高鸟辅。
reference:https://github.com/Jiangjao/python_learn_demo/blob/master/%E9%80%92%E4%? ? ? ? ? ? ? ? ? BB%A3%E4%B8%8E%E5%88%86%E6%B2%BB
? ? ? ? ? ? ? ? ?極客時間 《程序員的數(shù)學基礎課》
