归并排序的递归和迭代方法实现，C++版

1.归并排序理论
基本思想是将两个已排序的表归并为一个有序表。归并排序也是分治策略的思想体现。
（1）按递归的方法，从上向下的角度来思考，把待排序表一分为二，然后将分割后的两个表再次平分，直到分割后只剩下一个元素为止，然后将分割的结果进行两两归并，直到递归程序结束，排序完成
数据举例：
int arrIN[] = {98, 17, 38, 19, 22, 69, 45, 12, 65, 359, 984, 65, 32, 36};
二次划分
98, 17, 38, 19, 22, 69, 45￥￥12, 65, 359, 984, 65, 32, 36
二次划分
98, 17, 38, 19￥￥ 22, 69, 45￥￥12, 65, 359, 984￥￥65, 32, 36
二次划分
98, 17,￥￥38, 19￥￥ 22, 69￥￥ 45￥￥12, 65,￥￥359, 984￥￥65, 32,￥￥36
二次划分
98,￥￥17,￥￥38,￥￥19￥￥ 22, ￥￥69￥￥ 45￥￥12, ￥￥65,￥￥359, ￥￥984￥￥65, ￥￥32,￥￥36
递归到底
回溯进行归并
17,98,￥￥19,38, ￥￥ 22, 69￥￥ 45￥￥12, 65,￥￥359, 984￥￥ 32,65,￥￥36
回溯进行归并
17, 19, 38, 98￥￥  22, 45, 69￥￥12, 65, 359, 984￥￥32, 36,65
回溯进行归并
17, 19, 22, 38, 45, 69, 98￥￥12, 32, 36, 65, 65, 359, 984
回溯进行归并
12 ,17 ,19 ,22 ,32 ,36 ,38 ,45 ,65 ,65 ,69 ,98 ,359 ,984
回溯到最外层，递归结束，排序结束！！
（2）按迭代的方法，从下向上的角度来思考，首先把待排序表中每个元素都看作一个有序表，然后将元素两两归并，然后把操作后的表中元素每对儿看作是一个有序表，然后再以对儿为基础两两归并，同理直到将所有元素归并为一个有序表，排序结束
数据举例：
int arrIN[] = {98, 17, 38, 19, 22, 69, 45, 12, 65, 359, 984, 65, 32, 36};
第一次迭代：每2个归并为一组
count 1 : ,17 ,98 ￥￥19 ,38 ￥￥22 ,69 ￥￥12 ,45 ￥￥65 ,359 ￥￥65 ,984 ￥￥32 ,36
第二次迭代：每4个归并为一组
count 2 : ,17 ,19 ,38 ,98 ￥￥12 ,22 ,45 ,69￥￥65 ,65 ,359 ,984 ￥￥32 ,36
第三次迭代：每8个归并为一组
count 3 : ,12 ,17 ,19 ,22 ,38 ,45 ,69 ,98￥￥32 ,36 ,65 ,65 ,359 ,984
第四次迭代：每16个归并为一组
count 4 : ,12 ,17 ,19 ,22 ,32 ,36 ,38 ,45 ,65 ,65 ,69 ,98 ,359 ,984
迭代结束，排序结束！！
2.C++代码实现：
递归代码：

/*****************************
filename: recurMerge.cpp
description: realize merge sort in recursion mode
author: warrior mail:[e-mail]
date:2016-2-21
log:
*****************************/

/****** include *******/
#include "recurMerge.h"
using namespace std;
/****** define *********/
/****** variable ********/
/****** function *******/
/****************
description: realize merge sort in recursion mode
input:
    int * arrIN
    const int left
    const int right
output:
    none
****************/
void recurMergeSort(int* arrIN, const int leftSide, const int rightSide)
{
    int mid;
    if(leftSide<rightSide)
    {
        mid = (leftSide+rightSide)/2;
        recurMergeSort(arrIN, leftSide, mid);
        recurMergeSort(arrIN, mid+1, rightSide);
        mergeTwo2One(arrIN, leftSide,
                    arrIN, leftSide, mid,
                    arrIN, mid+1, rightSide);
    }
}
/****************
description: merge two sorted list to one sorted list
input:
    int * arrOUT, int arrOUT_start
    int * arrIN1, int arrIN1_start, int arrIN1_end
    int * arrIN2, int arrIN2_start, int arrIN2_end
output:
    none
****************/
void mergeTwo2One(
                int * arrOUT, const int arrOUT_start,
                int * arrIN1, const int arrIN1_start, const int arrIN1_end,
                int * arrIN2, const int arrIN2_start, const int arrIN2_end)
{
    int i,j,k=0;
    int tempARR[arrIN1_end-arrIN1_start + arrIN2_end-arrIN2_start +2];//= new int();
    i = arrIN1_start;
    j = arrIN2_start;
    k = 0;
    while((i<=arrIN1_end) && (j<=arrIN2_end))
    {
        if(arrIN1[i]<arrIN2[j])
        {
            tempARR[k] = arrIN1[i];
            k++;
            i++;
        }
        else
        {
            tempARR[k] = arrIN2[j];
            k++;
            j++;
        }
    }
    while(i<=arrIN1_end)
    {
        tempARR[k] = arrIN1[i];
        k++;
        i++;
    }
    while(j<=arrIN2_end)
    {
        tempARR[k] = arrIN2[j];
        k++;
        j++;
    }
    for(int h=0; h<k; h++)
    {
        arrOUT[arrOUT_start+h] = tempARR[h];
        cout<<" ,"<<tempARR[h];
    }
    cout<<endl;
    //delete tempARR;
}

#ifndef _RECURMERGE_H_
#define _RECURMERGE_H_
/****** include *******/
#include <iostream>
#include <stdio.h>
#include<fstream>
/****** define *********/
/****** variable ********/
/****** function *******/
void recurMergeSort(int* arrIN, const int leftSide, const int rightSide);
void mergeTwo2One(
                int * arrOUT, const int arrOUT_start,
                int * arrIN1, const int arrIN1_start, const int arrIN1_end,
                int * arrIN2, const int arrIN2_start, const int arrIN2_end);
#endif // _RECURMERGE_H_

迭代代码：

/*****************************
filename: recurMerge.cpp
description: realize merge sort in iteration mode
author: warrior mail:[e-mail]
date:2016-2-21
log:
*****************************/

/****** include *******/
#include "iteraMerge.h"
#include "recurMerge.h"
using namespace std;
/****** define *********/
/****** variable ********/
/****** function *******/
/****************
description: realize merge sort in iteration mode
input:
    int * arrIN
    const int arrLength
output:
    none
****************/
void iteraMergeSort(int* arrIN, const int arrLength)
{
    int stepLength = 1;
    int currentIndex = 0;
    int i=0;
    //ofstream outputFile;
    //outputFile.open("output.txt");
    while(stepLength<arrLength)
    {
        stepLength *= 2;
        mergeOnce(arrIN, arrLength, stepLength);
        cout<<"count "<<int(log(stepLength)/log(2))<<" :";
        //outputFile<<"count "<<int(log(stepLength)/log(2))<<" :";
        for(i=0; i<arrLength; i++)
        {
            cout<<" ,"<<arrIN[i];
            //outputFile<<" ,"<<arrIN[i];
        }
        //outputFile<<"\n";
        cout<<endl;
    }
    //outputFile.close();
    for(i=0; i<arrLength; i++)
    {
        cout<<" ,"<<arrIN[i];
    }
    cout<<endl;
}

/****************
description: excute once merge sort
input:
    int * arrIN
    const int arrLength
    const int stepLongth
output:
    none
****************/
void mergeOnce(int* arrIN, const int arrLength, const int stepLength)
{
    int iteratorNum = stepLength;
    int i=0;
    if(arrLength%iteratorNum == 0)
    {
        for(i=0; i<arrLength; i+=iteratorNum)
        {
            mergeTwo2One(
                        arrIN, i,
                        arrIN, i, i+iteratorNum/2-1,
                        arrIN, i+iteratorNum/2, i+iteratorNum-1);
        }
    }
    else
    {
        for(i=0; i<(arrLength-arrLength%iteratorNum); i+=iteratorNum)
        {
            mergeTwo2One(
                        arrIN, i,
                        arrIN, i, i+iteratorNum/2-1,
                        arrIN, i+iteratorNum/2, i+iteratorNum-1);
        }
        if(arrLength%iteratorNum > iteratorNum/2)
        {
            mergeTwo2One(
                        arrIN, i,
                        arrIN, i, i+iteratorNum/2-1,
                        arrIN, i+iteratorNum/2, arrLength-1);
        }
    }

}

#ifndef _ITERAMERGE_H_
#define _ITERAMERGE_H_
/****** include *******/
#include <iostream>
#include <stdio.h>
#include <math.h>
#include<fstream>
/****** define *********/
/****** variable ********/
/****** function *******/
void iteraMergeSort(int* arrIN, const int arrLength);
void mergeOnce(int* arrIN, const int arrLength, const int stepLength);
#endif // _ITERAMERGE_H_

主函数：

#include "recurMerge.h"
#include "iteraMerge.h"

using namespace std;

int main()
{
    int arrIN1[] = {98, 17, 38, 19, 22, 69, 45, 12, 65, 359, 984, 65, 32, 36};
    int arrIN2[] = {98, 17, 38, 19, 22, 69, 45, 12, 65, 359, 984, 65, 32, 36};
    int leftSide = 0;
    int rightSide = sizeof(arrIN1)/sizeof(int) - 1;
    cout << "arr lenght :" << sizeof(arrIN2)/sizeof(int)<<endl;
    recurMergeSort(arrIN1, leftSide, rightSide);
    iteraMergeSort(arrIN2, sizeof(arrIN2)/sizeof(int));

    return 0;
}

3.总结
（1）思考了递归与迭代的两种逆向思维
（2）理解了分治策略的实践
（3）程序中尝试了C++中I/O文件操作方法
     参考链接：http://blog.csdn.net/mak0000/article/details/3230199