??歸并排序(Merge Sort)原理：將當(dāng)前數(shù)組拆分成兩個子數(shù)組，一直拆分到每個數(shù)組只有一個元素再重新依次有序合并的過程。
??歸并排序(Merge Sort)核心思想：兩個有序數(shù)組合并為一個有序數(shù)組。

- (void)mergeArrayWithBegain:(NSInteger)begain mid:(NSInteger)mid end:(NSInteger)end
{
    NSInteger li = 0, le = mid - begain; // 左邊的子數(shù)組下標(biāo)
    NSInteger ri = mid, re = end; // 右邊的子數(shù)組下標(biāo)
    NSInteger ai = begain; // 待合并成數(shù)組起始下標(biāo)
    
   // 將左子數(shù)組備份
    NSMutableArray *mArray = [NSMutableArray array];
    for (NSInteger i = li; i < le; i++) {
        [mArray addObject:self.sortArray[begain + I]];
    }
    
  // 因為左右子數(shù)組是有序的，只需要從頭開始比較左右子數(shù)組即可，哪個小哪個放入數(shù)組中，同時下標(biāo)向后移動一位。 
    while (li < le) {
        if (ri < re && [self compareObjcet:self.sortArray[ri] anotherObject:mArray[li]]) {
            self.sortArray[ai++] = self.sortArray[ri++];
        } else {
            self.sortArray[ai++] = mArray[li++];
        }
    }
}

至于拆分與合并都是遞歸調(diào)用的過程：

- (void)sortArrayWithBegin:(NSInteger)begain end:(NSInteger)end
{
    if (end - begain >= 2) {
        NSInteger mid = (begain + end) >> 1;
        // 遞歸拆分左子數(shù)組
        [self sortArrayWithBegin:begain end:mid];
        // 遞歸拆分右子數(shù)組
        [self sortArrayWithBegin:mid end:end];
        // 合并數(shù)組
        [self mergeArrayWithBegain:begain mid:mid end:end];
    }
}

整體的排序操作其實就是簡單的給出最大數(shù)組

- (void)sort
{
    NSInteger arrayCount = self.sortArray.count;
    [self sortArrayWithBegin:0 end:arrayCount];
}

總結(jié)：歸并排序中無疑用到的就是遞歸調(diào)用。其時間復(fù)雜度計算方式 T(n) = 2 * T(n/2) + O(n);最后計算得 T(n) = O(nLogn);

T (n) =2?T (n/2) +O(n) 
T1 =O(1) 
T (n) /n =T (n/2) /(n/2)+O(1)

?令Sn =T(n)/n 
S1 =O(1) 
S (n) =S (n/2) +O(1)=S (n/4) +O(2)=S (n/8) +O(3)=S (n/2^k) +O(k) =S (1) +O(logn)=O(logn) 

T (n) =n?S (n) =O(nlogn)

同時附上常見的遞推式及復(fù)雜度對應(yīng)表：

常見的遞推式及復(fù)雜度