#include <iostream.h>
template <class Etype>
void
Merge( Etype A[ ], Etype TmpArray[ ], int LeftPos,
int RightPos, int RightEnd )
{
int LeftEnd = RightPos - 1;
int TmpPos = LeftPos;
int NumElements = RightEnd - LeftPos + 1;
while( LeftPos <= LeftEnd && RightPos <= RightEnd )
if( A[ LeftPos ] <= A[ RightPos ] )
TmpArray[ TmpPos++ ] = A[ LeftPos++ ];
else
TmpArray[ TmpPos++ ] = A[ RightPos++ ];
while( LeftPos <= LeftEnd ) TmpArray[ TmpPos++ ] = A[ LeftPos++ ];
while( RightPos <= RightEnd ) TmpArray[ TmpPos++ ] = A[ RightPos++ ];
for( int i = 0; i < NumElements; i++, RightEnd-- )
A[ RightEnd ] = TmpArray[ RightEnd ];
}
template <class Etype>
void
MergeSort( Etype A[ ], Etype TmpArray[ ], int Left, int Right )
{
if( Left < Right )
{
int Center = ( Left + Right ) / 2;
MergeSort( A, TmpArray, Left, Center );
MergeSort( A, TmpArray, Center + 1, Right );
Merge( A, TmpArray, Left, Center + 1, Right );
}
}
template <class Etype>
void
MergeSort( Etype A[ ], int N )
{
try
{
Etype *TmpArray = new Etype[ N ];
MergeSort( A, TmpArray, 0, N - 1 );
delete [ ] TmpArray;
}
catch( ... )
{
cerr << "Out of memory!! Sort fails." << endl;
}
}