アルゴリズム学習のソート(6)--ソートのマージ

一.アルゴリズムの説明
集計ソートは、1つのシーケンスを2つの長さの等しいサブシーケンスに分割し、各サブシーケンスの集計ソートを呼び出してソートし、それらを1つのシーケンスにマージします.2つのサブシーケンスをマージするプロセスを集計と呼び、集計ソートの実行時間は入力配列の要素との組合せに依存しません.
集計ソートは常に再帰的に呼び出され、サブシーケンスをソートします.再帰的に終了する条件は、配列に要素が1つしか含まれていない場合、関数は他の操作を行わずに直接戻ります.
二.時間の複雑さ
集計ソートは毎回、シーケンスを等しい2つのサブシーケンスに分割するので、集計ソートの時間的複雑さは、入力配列中の要素がソートされているかどうかに関係なく、最良の場合、平均および最悪の場合の時間的複雑さはO(nlogn)である.
三.くうかんふくざつさ
集計ソートの集計プロセスでは2つのサブシーケンスを集計する必要があり,配列のような構造を用いてデータを格納する場合は,2つのサブシーケンスを余分な空間にコピーして集計する必要があるため,格納構造として配列を用いると空間複雑度はO(n)となる.データの格納構造としてチェーンテーブルを使用する場合、2つのサブシーケンスを集計するプロセスは、チェーンテーブルの要素を別のチェーンテーブルに配置するだけであり、要素の値をコピーする必要はなく、空間的複雑度はO(1)である.
四.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);
}

五.参考文献
[1] Shaffer C A. Practical Introduction to Data Structure and Algorithm Analysis (C++ Edition)[J]. 2002.
[2]科曼and金貴、アルゴリズム導論:機械工業出版社、2006.
[3]T.H.Cormen,C.E.Leiserson,R.L.Rivest,and C.Stein,「アルゴリズム導論(影印版)」,ed:北京:高等教育出版社.