マージソートサンプル (ひどい実装です)

AppMain.cpp

#include <iostream>
#include <ctime>
#include <cstdio>
#include "MergeSort.h"

static const int DataSize = 100;

static void initRand()
{
    srand((unsigned int)time(NULL));
}

static int genRand( int size )
{
    return rand() % size;
}

int main( int argc, char* argv[] )
{
    int data[DataSize];

    initRand();
    for ( int i = 0; i < DataSize; i++ )
    {
        data[i] = genRand(DataSize);
    }
    std::cout << "Before------" << std::endl;
    for ( unsigned int i = 0; i < sizeof(data)/sizeof(int); i++ )
    {
        std::cout << data[i] << "\t";
    }
    std::cout << std::endl;
    MergeSort<int> merge( data, sizeof(data)/sizeof(int) );
    
    std::cout << "Result------" << std::endl;
    for ( unsigned int i = 0; i < sizeof(data)/sizeof(int); i++ )
    {
        std::cout << data[i] << "\t";
    }
    std::cout << std::endl;

    return 0;
}

MergeSort.h

#pragma once

#include <iostream>

template <class X>
class MergeSort
{
public:
    MergeSort( X* data, int size );
    ~MergeSort(void);
private:
    void devide( X* data, int size );
    void merge( X* data1, int l, X* data2, int r, X* data );
    inline void sizeLR( int size, int* left, int* right )
    {   
        *left  = size / 2;  *right = size - *left;
    }
};

template <class X>
MergeSort<X>::MergeSort( X* data, int size )
{
    devide( data, size );
}


template <class X>
MergeSort<X>::~MergeSort(void)
{
}

template <class X>
void MergeSort<X>::devide( X* data, int size )
{
    int left, right;
    sizeLR(size, &left, &right);
    X* data1 = new X[left ];
    X* data2 = new X[right];

    for ( int i = 0; i < left; i++ )
    {
        data1[i] = data[i];
    }
    for ( int i = 0; i < right; i++ )
    {
        data2[i] = data[i+left];
    }

    if ( left  != 1 )
    {
        devide( data1, left  );
    }
    if ( right != 1 )
    {
        devide( data2, right );
    }

    merge( data1, left, data2, right, data );
    delete data1;   data1 = NULL;
    delete data2;   data2 = NULL;
}

template <class X>
void MergeSort<X>::merge( X* dl, int l, X* dr, int r, X* data )
{
#ifdef _DEBUG
    std::cout << __FUNCTION__ << std::endl;
    for ( int i = 0; i < l; i++ )   std::cout << dl[i] << "\t";
    std::cout << std::endl;
    for ( int i = 0; i < r; i++ )   std::cout << dr[i] << "\t";
    std::cout << std::endl;
#endif
    int lc = 0, rc = 0;
    for ( int i = 0; i < l + r; i++ )
    {
        if ( dl[lc] <= dr[rc] )
        {
            if ( lc < l ) // within range
            {
                data[i] = dl[lc];
                lc++;
            }
        }
        else
        {
            if ( rc < r ) // within range
            {
                data[i] = dr[rc];
                rc++;
            }
        }
    }
    // assign remaining value 
    if ( lc != l ) data[ l + r - 1 ] = dl[ l - 1 ];
    //if ( rc != r ) data[ l + r - 1 ] = dr[ r - 1 ]; // こっちの条件になることはない
#ifdef _DEBUG
    for ( int i = 0; i < l + r; i++ )   std::cout << data[i] << "\t";
    std::cout << std::endl;
#endif
}