歸并排序（mergeSort）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應用痕慢。查看完整代碼
1.算法思想：將待排序元素坑傅，分成若干子序，然后在將子序排序成有序窥浪。將已有序的子序列合并躏升，得到完全有序的序列惧财；即先使每個子序列有序宋税，再使子序列段間有序。
2.算法步驟：
(1)坪圾、比較arr[i]和arr[j]的大小晓折，若arr[i]≤arr[j]，則將第一個有序表中的元素arr[i]復制到temp[k]中兽泄，并令i和k分別加上1漓概；否則將第二個有序表中的元素arr[j]復制到temp[k]中，并令j和k分別加上1病梢，
(2)胃珍、如此循環(huán)下去，直到其中一個有序表取完蜓陌。
(3)觅彰、再將另一個有序表中剩余的元素復制到temp中從下標k開始。
(4)护奈、將temp里面的元素合并到arr中缔莲。
歸并排序的算法我們通常用遞歸實現哥纫，先把待排序區(qū)間[s,t]以中點二分霉旗，接著把左邊子區(qū)間排序，再把右邊子區(qū)間排序蛀骇，最后把左區(qū)間和右區(qū)間用一次歸并操作合并成有序的區(qū)間[s,t]厌秒。
3.算法詳解
初始狀態(tài)：6,2,8,10,8,9,1
第一次歸并后：{6,2},{8,10},{8,9},{1}
第二次歸并后：{2,6,8,10}，{1,8,9}擅憔；
第三次歸并后：{1,2,6,8,8,9,10}鸵闪；
排序結束
4.算法分析：
時間復雜度：對一個數組，分成小區(qū)間需要logN暑诸，每一次都有歸并操作蚌讼，所以歸并排序在O(N*logN)
穩(wěn)定性：是穩(wěn)定的排序算法
