Merge Sort (归并排序）-蒲公英云

Merge Sort (归并排序）

归并排序是分治法的例子。

在归并排序中，会递归地把列表一分为2，然后进行排序，最后再合并。

归并排序中，需要使用辅助空间O(n)。

比如，要对3，5，4，9，2进行排序，我们有下图

![Image 1][]

不断地把n/2,然后进行排序和合并，程序如下所列：

<pre name="code" class="java">//
//  main.cpp
//  MergeSort
//
//  Created by Paul Huang on 15/5/10.
//  Copyright (c) 2015年 Paul Huang. All rights reserved.
//
#include <iostream>
int data[5]={3,5,4,9,2};
int dataaux[5];
int max(int x, int y)
{
    if(x > y)
    {
        return true;
    }
    else
    {
        return false;
    }
}
void merge( int low, int mid, int high ){
    int i=low;
    int j=mid+1;
    for(int k=low;k<=high;k++){
        dataaux[k]=data[k]; //复制数组元素到一个新数组
    }
    for(int k=low;k<=high;k++){
        if(i>mid) data[k]=dataaux[j++];   //左边（低位）的数组已经全部比较完，并进入比较后的结果数组
        else if (j>high) data[k]=dataaux[i++]; //右边（高位）的数组已经全部比较完，并进入比较后的结果数组
        else if(max(dataaux[i],dataaux[j])) data[k]=dataaux[j++];  //左边和右边的数组进行比较
        else data[k]=dataaux[i++];
    }
    }
void sort(int left, int right)
{
    if(right<=left) return;
    int mid=left+(right-left)/2;
    sort(left,mid);
    sort(mid+1,right);
    merge(left,mid,right);
 }
int main(int argc, const char * argv[]) {
    // insert code here...
    std::cout << "Hello, World!\n";
    sort(0,4);
    for(int i=0;i<5;i++){
        std::cout<<data[i]<<std::endl;
    }
    return 0;
}