数据结构与算法——Merge Sort

#include <iostream>

void Merge(int A[], int l, int mid, int h){
    int i, j, k;
    i = l; j = mid + 1; k = l;
    int B[h+1];
    while(i <= mid && j <= h){
        if(A[i] < A[j]){
            B[k++] = A[i++];
        }
        else{
            B[k++] = A[j++];
        }
    }
    for(; i <= mid; i++){
        B[k++] = A[i];
    }
    for(; j <= h; j++){
        B[k++] = A[j];
    }
    for(i = l; i <= h; i++){
        A[i] = B[i];
    }
}

// 迭代
void IMergeSort(int A[], int n)
{
    int p, i, l, mid, h;
    for(p = 2; p <= n; p = p * 2){
        for(i = 0; i + p - 1 < n; i = i + p){
            l = i;
            h = i + p -1;
            mid = (l + h) / 2;
            Merge(A, l, mid, h);
        }
        if(i < n){
            l = i;
            h = n-1;
            mid = (l+h)/2;
            Merge(A,l,mid,h);
        }
        for(int i = 0; i < n; ++i){
            std::cout<<A[i] << " ";
        }
        std::cout << "\n";
    }
    if(p/2 < n){
        Merge(A, 0, p/2-1, n-1);
    }
}

// 递归
void MergeSort(int A[], int l, int h){
    int mid;
    if(l < h){
        mid = (l + h) / 2;
        MergeSort(A, l, mid);
        MergeSort(A, mid+1, h);
        Merge(A, l, mid, h);
    }
}

int main()
{
    int A[] = {8, 3, 7, 4, 9, 2, 6, 5, 1, 11, 10};
    int n = 11;
    IMergeSort(A, n);
    
    for(int i = 0; i < n; ++i){
        std::cout<<A[i] << " ";
    }

    return 0;
}

3 8 4 7 2 9 5 6 1 11 10 
3 4 7 8 2 5 6 9 1 10 11 
2 3 4 5 6 7 8 9 1 10 11 
1 2 3 4 5 6 7 8 9 10 11