マージソート

マージソート

VC++.NET | VC++.NET 2005

using namespace System;
using namespace System::Collections;


static void marge( array<String^>^ ary, 
                   array<String^>^ ary1,
                   array<String^>^ ary2 ) {
    
    int i = 0;
    int j = 0;
    int k = 0;
    while(i < ary1->Length && j < ary2->Length ) {
        if ( ary1[i]->CompareTo(ary2[j]) < 0 ) {
            ary[k++] = ary1[i++];
        } else {
            ary[k++] = ary2[j++];
        }
    }
    while(i < ary1->Length ) {
        ary[k++] = ary1[i++];
    }
    while(j < ary2->Length ) {
        ary[k++] = ary2[j++];    
    }
}

static void margeSort( array<String^>^ ary ) {
    
    if (ary->Length > 1) {
        int m = ary->Length / 2;
        int n = ary->Length - m;
        array<String^>^ a1 = gcnew array<String^>(m);
        array<String^>^ a2 = gcnew array<String^>(n);
        
        for (int i=0; i<m; i++) {
            a1[i] = ary[i];
        }
        for (int i=0; i<n; i++){
            a2[i] = ary[m + i];
        }
        margeSort(a1);
        margeSort(a2);
        marge(ary, a1, a2);
    }
}

static void sort( array<String^>^ ary ) {

    margeSort(ary);

}

static void print( array<String^>^ ary ) {

    for (int i=0; i<ary->Length; i++) {
        Console::WriteLine(ary[i]);
    }
}

int main(array<System::String ^> ^args)
{
    
    String^ line;
    IList^ list = gcnew ArrayList();
    
    while ( (line = Console::ReadLine()) != nullptr ) {
        list->Add(line);
    }
    
    array<String^>^ ary = gcnew array<String^>(list->Count);
    list->CopyTo(ary, 0);
    
    sort(ary);
    print(ary);    
    return 0;
}