The Recursive Binary Merge Sort: C++ source code

By Sergey Skudaev

Recursive Binary Merge Sort, implementation in C++
Date:3/26/2000   

#include <iostream>
#include <toolhelp.h>     //GetTickCount()  is valid only for Borland C++


void printArray ( int array [], int last );
void recursive_bin_merge ( int array [], int last, int &cells );
void resetArray(int array[], int last);
void merge(int array[], int listUp[], int listDn[], int index, int cells,              
                                                                                 int idxUp, int  idxDn);
intmain(int argc, char* argv[])
{
    int array[] = {75, 55, 15, 20, 85, 30, 35, 10, 60, 40, 50, 25, 45, 80, 70, 65};
    int last = 16;
    int cells = 1;
    long lstart= 0;
    long lend = 0;
                                printArray ( array, last  );

                                lstart = GetTickCount( );

                                recursive_bin_merge ( array, last, cells);

                                lend = GetTickCount();

                                int takes;
                                takes = lend - lstart;

    cout<<"\nIt takes "<<takes<<" msec to sort the array of 16 integers"<<endl;

   int hold = 1;
    cin >> hold;

}



void recursive_bin_merge(int array[], int last, int &cells)
{
        int current = 0;
        int new_current = 0;
        int listUp[]= {0,0,0,0,0,0,0,0};
        int listLow[]= {0,0,0,0,0,0,0,0};

        if (cells <= last/2)
        {
                while (current < last)
                {
                        for ( int i = 0; i< cells; i ++)
                        listUp [new_current + i] = array [current + i];

                     current = current + cells;

                        for (int j = 0; j<cells; j++)
                        listLow [new_current+j] = array [current + j];

                    current = current + cells;

                    new_current = new_current + cells;
                }

                            printArray ( listUp, 8);
                            printArray ( listLow, 8);

                            resetArray ( array, last);


                            int index =0;
                            int count = cells;
                            int idxUp = 0;
                            int idxDn = 0;
                            int t = 0;

                        while (index < last)
                        {
                            t = t+1;
                                merge(array, listUp, listLow, index, count, idxUp, idxDn);
                                index = index + 2*cells;
                                idxUp = idxUp + cells;
                                idxDn = idxDn + cells;
                                count = count + cells;

                            }

                            cells = cells * 2;
                            cout<<"Merge_Times :"<<t<<endl;

                            printArray(array, last);

                            recursive_bin_merge( array, last, cells);

            } //end if
}

void printArray(int array[],int last)
{
    for ( int i = 0; i < last; i++)

    cout<<array[i]<<",";

    cout<<endl;
}



void resetArray( int array[], int last)
{
        for ( int i = 0; i< last;i++ )

        array[i] = 0;
}




void merge ( int array[], int listUp[], int listDn[], int index, int cells, 

                                                                                        int idxUp, int idxDn)
{


while ((idxUp < cells)&&(idxDn < cells))
{

            if ( listUp [idxUp] < listDn [idxDn] )
            {
            array [index] = listUp [idxUp];
            index++;
            idxUp++;
            }
            else
            {
            array [index] = listDn [idxDn];
            index++;
            idxDn++;
            }

        }

        while (idxUp < cells)
        {
        array [index] = listUp [idxUp];
        index++;
        idxUp++;
        }

        while (idxDn < cells)
        {
        array [index] = listDn [idxDn];
        index++;
        idxDn++;
        }

}

Demo Applet

My eBooks on Amazon.com