归并排序

#include <iostream>
#include "iomanip"

using namespace std;

void merge(int a[] , int b[] ,int low , int mid , int high)
{
    int i , j , k;
    for(int k = low ; k <= high ; k++)
        b[k] = a[k];
    //因为在merge两个数组的时候，a[k++] = b[i++];
    //排好序的元素是放入a[]而不是更新b数组
    for(i = low , j = mid+1 , k = i ; i <= mid && j <= high ; k++)
    {
        if(b[i] <= b[j])
            a[k] = b[i++];
        else
            a[k] = b[j++];
    }
    while(i <= mid) a[k++] = b[i++];
    while(j <= high) a[k++] = b[j++];
}

void MergeSort(int a[] , int b[] , int low , int high)
{
    if(low < high)
    {
        int mid = (low + high)/2;//选取中间元素进行划分两个子序列
        MergeSort(a , b ,low , mid);
        MergeSort(a , b, mid+1 , high);
        merge(a , b ,low , mid , high);
    }
}

int main()
{
    int a[10] = {1,9,2,0,12,4,5,3,7,10};
    int b[10] = {1,9,2,0,12,4,5,3,7,10};
    MergeSort(a , b , 0 , 9);
    for(int i = 0 ; i < 10 ; i++)
        printf("%d ",a[i]);
}