二.时间复杂度

三.空间复杂度

四.C++实现

#include <iostream>

#include "Sort.h"
#include "randomarray.h"

bool Merge(std::vector<int>::iterator Ite, int LeftIndex, int RightIndex)
{
    if (LeftIndex >= RightIndex)
    {
        return false;
    }

    if (LeftIndex == (RightIndex - 1))
    {
        return true;
    }


    int Mid = (LeftIndex + RightIndex) / 2;


    // copy the array
    std::vector<int> LeftArray;
    for (int Index = LeftIndex; Index < Mid; Index++)
    {
        int Tmp = *(Ite + Index);
        LeftArray.push_back(*(Ite + Index));
    }

    std::vector<int> RightArray;
    for (int Index = Mid; Index < RightIndex; Index++)
    {
        int Tmp = *(Ite + Index);
        RightArray.push_back(*(Ite + Index));
    }


    // merge the sub array
    for (int Index_left = 0, Index_right = 0, Index = LeftIndex;
    Index < RightIndex;
    Index++)
    {
        // Ended merge the left array
        if (Index_left >= LeftArray.size())
        {
            int Tmp = RightArray[Index_right];
            *(Ite + Index) = RightArray[Index_right++];
            continue;
        }

        // Ended merge the right array
        if (Index_right >= RightArray.size())
        {
            int Tmp = LeftArray[Index_left];
            *(Ite + Index) = LeftArray[Index_left++];
            continue;
        }

        // merge the two array
        if (RightArray[Index_right] > LeftArray[Index_left])
        {
            int Tmp = LeftArray[Index_left];
            *(Ite + Index) = LeftArray[Index_left++];
        }
        else
        {
            int Tmp = RightArray[Index_right];
            *(Ite + Index) = RightArray[Index_right++];
        }
    }

    return true;

}






bool MergeSort(std::vector<int>::iterator Ite, int LeftIndex, int RightIndex)
{
    // return false if the LeftIndex >= RightIndex
    if (LeftIndex >= RightIndex)
    {
        return false;
    }


    // return true when there are only one element in the array
    if (LeftIndex == (RightIndex - 1))
    {
        return true;
    }


    // split the array to two sub array
    int Mid = (LeftIndex + RightIndex) / 2;
    MergeSort(Ite, LeftIndex, Mid);
    MergeSort(Ite, Mid, RightIndex);

    // Merge the sub array
    return Merge(Ite, LeftIndex, RightIndex);

}


bool MergeSort(std::vector<int>& Array)
{
    int Size = Array.size();

    if (Size == 0)
    {
        return false;
    }

    if (Size == 1)
    {
        return true;
    }

    return MergeSort(Array.begin(), 0, Size);
}

五.参考文献