歸并排序（Merge sort枕稀，臺灣譯作：合并排序）是建立在歸并操作上的一種有效的排序算法劣像。
歸并算法的中心是歸并兩個已經(jīng)有序的數(shù)組蕾久，并且遞歸調(diào)用歸并操作
該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用舍杜。
優(yōu)點(diǎn)和缺點(diǎn)：
比簡單排序在速度上快很多；
歸并排序會占用雙倍的存儲空間桅滋。
效率：
歸并排序的時間復(fù)雜度是 O(N*LogN)慧耍；
簡單排序的復(fù)雜度是O(N2)。
每一趟歸并的時間復(fù)雜度為 O(n), 需要O(logn)次歸并
算法步驟：
1. 申請空間丐谋，使其大小為兩個已經(jīng)排序序列之和芍碧，該空間用來存放合并后的序列
2. 設(shè)定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置
3. 比較兩個指針?biāo)赶虻脑睾爬x擇相對小的元素放入到合并空間泌豆，并移動指針到下一位置
4. 重復(fù)步驟3直到某一指針達(dá)到序列尾
5. 將另一序列剩下的所有元素直接復(fù)制到合并序列尾
圖解
Paste_Image.png
