算法——归并排序（自顶向下、自底向上）

自顶向下

#include <iostream>
#include <algorithm>
#include "InsertionSort.h"

using namespace std;

template<typename T>
// 将arr[l...mid]和arr[mid+1...r]两部分进行归并
void __merge(T arr[] , int l, int mid, int r){
    T aux[r-l+1];
    // 将数组复制一份到aux[] 
    for( int i = l ; i <= r ; i ++ )
        aux[i-l] = arr[i];
    // 初始化，i、j指向左、右半部分的起始索引位置 
    int i = l, j = mid + 1;
    for( int k = l ; k <= r ; k ++ ){
        // 如果左半部分已处理完毕 
        if( i > mid){
            arr[k] = aux[j-l];
            j++; 
        }
        // 如果右半部分已处理完毕 
        else if( j > r){
            arr[k] = aux[i-l];
            i ++;
        }
        // 左半部分所指元素 < 右半部分所指元素 
        else if( aux[i-l] < aux[j-l] ){
            arr[k] = aux[i-l];
            i ++;
        }
        // 左半部分所指元素 >= 右半部分所指元素 
        else{
            arr[k] = aux[j-l];
            j++;
        }
    }
}

// 递归使用归并排序，对arr[l...r]的范围进行排序 
template<typename T>
void __mergeSort(T arr[] , int l, int r){
    
    if( l >= r)
        return; 
        
    int mid = (l+r)/2;
    __mergeSort(arr,l,mid);
    __mergeSort(arr,mid+1,r);
    // 优化，前后两部分有序时不归并 
    if( arr[mid] > arr[mid+1] )
        __merge(arr, l, mid, r);     
} 

template<typename T>
void mergeSort(T arr[] , int n){
    __mergeSort( arr , 0 , n-1 );
}

自底向上

//自底向上归并，可对链表排序 
template<typename T>
void mergeSortBU(T arr[], int n){
    for( int sz = 1 ; sz <= n ; sz += sz )
        for( int i = 0 ; i + sz < n ; i += sz + sz )
            // 对 arr[i...i+sz-1] 和 arr[i+sz...i+2*sz-1] 进行归并
            __merge( arr , i , i + sz - 1 , min(i + sz + sz -1,n-1));             
}

应用：求逆序对