/**
 *  @file merge_sort.h
 *  @brief  マージソート.
 *  @note
 *      安定ソート. ただし、ソート対象全体の半分のサイズのワークメモリが必要.
 */
#ifndef MERGE_SORT_H
#define MERGE_SORT_H

#include <cstddef>
#include <algorithm>
#include <functional>
#include <iterator>


// マージソートの内部処理. 他は使っちゃ駄目.
namespace merge_sort_detail {

// 挿入ソート. (Tが大きいとスタックにコピー(tmp)を作ることになるので、 再帰してるmerge_sort_body_外で実行)
template<typename BidiIte, class CMP>
void merge_sort_insertion_sort_(BidiIte first, BidiIte last, CMP cmp)
{
    typedef typename std::iterator_traits<BidiIte>::value_type T;
    BidiIte i = first;
    while (++i != last) {
        T       tmp( *i );
        BidiIte j = i;
        BidiIte k = i;
        do {
            --k;
            if (!cmp(tmp, *k))
                break;
            *j = *k;
            --j;
        } while (k != first);
        *j = tmp;
    }
}


template<typename BidiIte, class CMP, typename T>
void merge_sort_body_(BidiIte first, BidiIte last, CMP cmp, T* wk)
{
    std::size_t size = std::distance(first, last);
    if (size < 32) {    // 一定以下になったら、挿入ソートで並べ替え.
        if (size > 1)
            merge_sort_insertion_sort_(first, last, cmp);
        return;
    }

    // 前半後半に別けてソート.
    BidiIte     mid( first);
    std::size_t halfsize = size / 2;
    assert(halfsize > 0);
    std::advance(mid, halfsize);

    merge_sort_body_(first, mid , cmp, wk);     // 前半をソート.
    merge_sort_body_(mid  , last, cmp, wk);     // 後半をソート.

    // 前半後半がすでにソート済みであることを前提に並べ直し.
    {
        BidiIte     s( first );
        BidiIte     d( first );
        T*          wk_e     = wk + halfsize;
        T*          wp       = wk;

        // ワークに前半をコピー.
        while (wp != wk_e) {
            *wp++ = *s;
            ++s;
        }

        // 前半後半をみくらべて、元の領域へデータを詰めていく.
        wp = wk;
        do {
            if (cmp(*s, *wp)) {
                *d = *s;
                ++s;
            } else {
                *d = *wp++;
            }
            ++d;
        } while (s != last && wp != wk_e);

        if (wp != wk_e) {
            do {
                *d = *wp++;
                ++d;
            } while (wp != wk_e);
        }
      #if 0 // すでに詰まっているはず.
        else {
            do {
                *d = *s;
                ++d;
                ++s;
            } while (s != last);
        }
      #endif
    }
}


template<typename T>
struct merge_sort_work_mem_ {
    ~merge_sort_work_mem_() { delete[] p_; }
    T*      p_;
};

}   // namespace merge_sort_detail




/// マージソート.
template<typename BidiIte, class CMP>
void merge_sort(BidiIte first, BidiIte last, CMP cmp)
{
    typedef typename std::iterator_traits<BidiIte>::value_type T;
    std::size_t         size = std::distance(first, last);
    if (size < 48) {
        merge_sort_detail::merge_sort_insertion_sort_(first, last, cmp);
        return;
    }
    merge_sort_detail::merge_sort_work_mem_<T>  wk;
    wk.p_ = new T[ size / 2 ];
    merge_sort_detail::merge_sort_body_(first, last, cmp, wk.p_);
}


/// マージソート.
template<typename BidiIte> inline
void merge_sort(BidiIte first, BidiIte last) {
    merge_sort( first, last, std::less<typename std::iterator_traits<BidiIte>::value_type>() );
}



/// マージソート.  呼び元が作業バッファを与えるバージョン.
template<typename BidiIte, class CMP, typename T>
void merge_sort_with_buf(BidiIte first, BidiIte last, T* buf, std::size_t buf_size, CMP cmp)
{
    typedef typename std::iterator_traits<BidiIte>::value_type value_type;
    assert( (value_type*)0 == (T*)0 );
    assert( std::distance(first, last) <= 2 * buf_size );
    merge_sort_detail::merge_sort_body_(first, last, cmp, buf);
}


/// マージソート. 呼び元が作業バッファを与えるバージョン.
template<typename BidiIte, typename T> inline
void merge_sort_with_buf(BidiIte first, BidiIte last, T* buf, std::size_t buf_size) {
    merge_sort_with_buf( first, last, buf, buf_size, std::less<typename std::iterator_traits<BidiIte>::value_type>() );
}

#endif