Question

C++ sort a file with 140 integers where only 20 integers maybe placed into memory at any one time

Main idea: break data into blocks, sort blocks into runs, merge runs less. Call inFile1 our source file (the one with the initial 140 records to be sorted. You will also need an inFile2, and 2 other files outFile1 and outFile2. Break the file into blocks of size 20: in this case there will be 7 blocks ( 140/20 ) Sort the blocks by read a block, sort it, store in outFile1 read a block, sort it, store in outFile2 read a block, sort it, store in outFile1 ( in other words, sort a block and alternately place in the files outFile1, outFile2 ) By definition a run is a sorted block Note that each file outFile1 and outFile2 will have half of the runs Merge the runs Merge data from outFile1 and outFile2 to  inFile1 and inFile2. Merge the first run on outFile1 and the first run on outFile2, and store the result on inFile1: Read two records in main memory, compare, store the smaller on inFile1 Read the next record from either outFile1 or outFile2  the file that had its record moved/stored  to inFile1 Similarly merge the second run on outFile1 and the second run on outFile2, store the result on inFile2. Merge the third run on outFile1 and the third run on outFile2, store the result on inFile1... etc.    merging each run and storing the result alternatively on inFile1 and inFile2. At the end        inFile1 and inFile2 will contain sorted runs twice the size of the previous runs on outFile1 and outFile2 Now merge data from inFile1 and inFile2   to outFile1 and outFile2. Merge the first run on inFile1 and the first run on inFile2 and store the result on outFile1. Merge the second run on inFile1 and the second run on inFile2, store the result on outFile2 Etc, merge and store alternatively on inFile1 and inFile2. Repeat the process until only one run is obtained. This would be the sorted file

restrictions:

MUST use algorithms from sort_algorithms.t:

the algorithms may not be modified. - but you may assume an overloaded < operator exists. Thus you may remove the pointer to the function cmp ( obviously, the code will have to replace any reference to cmp, no puns intended, with < ) It is permissible to copy/paste any algorithms from sort_algorithms.t that you use to your own sort_alg.t Declare a variable MAX_MEM_SIZE, of type size_t. Initialize to 20 If you are really paying attention to the directions, you will realize that 2 arrays of 20 cannot both be in memory at the same time – depending on how you implement the above algorithm and which sort you use, you may need to break into blocks of size 10 a sample file to be sorted is provided.

Sort_algorithms.t

*****************************************************************************************

template

void mergesort1(T* arrayptr, const int& arraySize )

{

sortmerge1( arrayptr, arraySize, 0, arraySize - 1 );

}

*****************************************************************************************

template

void sortmerge1( T* arrayptr, const int& arraySize, int l, int r )

{

int mid, i, j, k;

if ( l < r )

    {

      mid = (r + l)/2;

      sortmerge1( arrayptr, arraySize, l, mid );

      sortmerge1( arrayptr, arraySize, mid + 1, r );

      T* temp = new T[ arraySize ];

      for ( i = mid + 1; i > l; i-- )

        temp[ i - 1 ]= arrayptr[ i - 1 ];

      for ( j = mid; j < r; j++ )

        temp[ r + mid - j ] = arrayptr[ j + 1 ];

      for ( k = l; k <= r; k++)

        arrayptr[k] = ( temp[i] < temp[j] ) ? temp[i++] : temp[j--];

    }

temp = 0;

delete [] temp;

}

*****************************************************************************************

template

void msSort( T* arrayptr, const int& arraySize )

{

T* copy = new T[ arraySize ];

int i;

for ( i = 0; i < arraySize; i++ )

    copy[i] = arrayptr[i];

mergesort2( copy, arrayptr, 0, arraySize - 1 );

}

*****************************************************************************************

template

void mergesort2( T* source, T* dest, int l, int r )

{

if ( l != r )

    {

      int mid = ( l + r )/2;

      mergesort2( dest, source, l, mid );

      mergesort2( dest, source, mid + 1, r );

      merge2( source, dest, l, mid, r );

    }

}

*****************************************************************************************

template

void merge2( T* source, T* arrayptr , int l, int mid, int r )

{

int i = l;

int j = mid + 1;

int k = l;

while ( ( i <= mid ) && ( j <= r ) )         // Compare current item from each list

    if ( source[ i ] < source[ j ] )          // Then i item comes first

      arrayptr[ k++ ] = source[ i++ ];

    else                                        // j item comes first

      arrayptr[ k++ ] = source[ j++ ];

                                      // Move what is left of remaining list

if ( i > mid )

    while ( j <= r )

      arrayptr[ k++ ] = source[ j++ ];

else

    while (i <= mid )

      arrayptr[ k++ ] = source[ i++ ];   

}

#endif

Answer 1

The C++ program is:

#include<bits/stdc++.h>

using namespace std;

struch Mmhn

{

int element;

int i;

};

void swap(Mhn* x,Mhn* y);

class Mh

{

Mhn* harr

int hsize;

public:

Mh(Mhn a[], int size);

void Mhify(int);

int left(int i) { return(2*i+1);}

int right(int i); .............................................................................................................

Remaining code is in pictures:This the total code requried to sort.