Code:
#include <cstdlib>
#include <iostream>
#include <ctime>
#define ORG
int * BottomUpMergeSortOrg(int a[], int b[], size_t n);
int * BottomUpMergeSortAlt(int a[], int b[], size_t n);
struct msptr
{
int *r;
int *e;
};
void Merge3012( msptr *p, int *&pax, int *&pbx, size_t & rsz );
void Merge201( msptr *p, int *& pax, int *&pbx, size_t &rsz );
void MergeCpy10( msptr *p, int *&pax, int *&pbx, size_t &rsz );
inline void Merge3013( msptr *p )
{
p[2] = p[3];
}
inline void Merge3023( msptr *p )
{
p[1] = p[2];
p[2] = p[3];
}
inline void Merge3123( msptr *p )
{
p[0] = p[1];
p[1] = p[2];
p[2] = p[3];
}
inline void Merge202( msptr *p )
{
p[1] = p[2];
}
inline void MergeCpy11( msptr *p )
{
p[0] = p[1];
}
inline void Merge212( msptr *p )
{
p[0] = p[1];
p[1] = p[2];
}
inline bool Merge32( msptr *p, int *&pbx )
{
*pbx++ = *p[2].r++; // run 2 smallest
if(p[2].r < p[2].e) return true; // if not end run continue
return false;
}
inline bool Merge40( msptr *p, int *&pbx)
{
*pbx++ = *p[0].r++;
if ( p[0].r < p[0].e ) return true;
Merge3123( p );
return false;
}
inline bool Merge41( msptr *p, int *&pbx )
{
*pbx++ = *p[1].r++;
if ( p[1].r < p[1].e ) return true;
Merge3023( p );
return false;
}
inline bool Merge42( msptr *p, int *&pbx )
{
*pbx++ = *p[2].r++; // run 2 smallest
if ( p[2].r < p[2].e ) return true;
Merge3013( p );
return false;
}
inline bool Merge43( msptr *p, int *&pbx )
{
*pbx++ = *p[3].r++;
if ( p[3].r < p[3].e ) return true;
return false;
}
void Merge201( msptr *p, int *& pax, int *&pbx, size_t &rsz )
{
while(1)
{
if(*p[0].r <= *p[1].r)
{
*pbx++ = *p[0].r++; // run 0 smallest
if(p[0].r >= p[0].e) // if not end run continue
{
MergeCpy11( p );
break;
}
}
else
{
*pbx++ = *p[1].r++; // run 1 smallest
if(p[1].r >= p[1].e) // if not end run continue
{
break;
}
}
}
MergeCpy10( p, pax, pbx, rsz );
}
void MergeCpy10( msptr *p, int *& pax, int *&pbx, size_t &rsz )
{
*pbx++ = *p[0].r++; // copy element
while (p[0].r < p[0].e)
{
*pbx++ = *p[0].r++; // copy element
}
pax += rsz << 2; // setup for next set of runs
}
int * BottomUpMergeSortAlt(int a[], int b[], size_t n)
{
std::cout << "New...." << std::endl;
msptr p[4];
int *pax; // ptr to set of runs in a
int *pbx; // ptr for merged output to b
size_t rsz = 1;
if(n < 2)
return a;
if(n == 2)
{
if(a[0] > a[1])std::swap(a[0],a[1]);
return a;
}
if(n == 3)
{
if(a[0] > a[2])std::swap(a[0],a[2]);
if(a[0] > a[1])std::swap(a[0],a[1]);
if(a[1] > a[2])std::swap(a[1],a[2]);
return a;
}
while(rsz < n)
{
pbx = &b[0];
pax = &a[0];
while(pax < &a[n])
{
p[0].e = rsz + (p[0].r = pax);
if(p[0].e >= &a[n])
{
p[0].e = &a[n];
MergeCpy10( p, pax, pbx, rsz );
Merge201( p, pax, pbx, rsz );
continue;
}
p[1].e = rsz + (p[1].r = p[0].e);
if(p[1].e >= &a[n])
{
p[1].e = &a[n];
Merge201( p, pax, pbx, rsz );
continue;
}
p[2].e = rsz + (p[2].r = p[1].e);
if(p[2].e >= &a[n])
{
p[2].e = &a[n];
Merge3012( p, pax, pbx, rsz );
Merge201( p, pax, pbx, rsz );
continue;
}
p[3].e = rsz + (p[3].r = p[2].e);
if(p[3].e >= &a[n])
{
p[3].e = &a[n];
}
// 4 way merge
while(1)
{
if(*p[0].r <= *p[1].r )
{
if(*p[2].r <= *p[3].r)
{
if(*p[0].r <= *p[2].r)
{
if ( !Merge40( p, pbx ) ) break;
}
else
{
if ( !Merge42( p, pbx ) ) break;
}
}
else
{
if(*p[0].r <= *p[3].r)
{
if ( !Merge40( p, pbx ) ) break;
}
else
{
if ( !Merge43( p, pbx ) ) break;
}
}
}
else
{
if(*p[2].r <= *p[3].r)
{
if(*p[1].r <= *p[2].r)
{
if ( !Merge41( p, pbx ) ) break;
}
else
{
if ( !Merge42( p, pbx ) ) break;
}
}
else
{
if(*p[1].r <= *p[3].r)
{
if ( !Merge41( p, pbx ) ) break;
}
else
{
if ( !Merge43( p, pbx ) ) break;
}
}
}
}
// 3 way merge
Merge3012( p, pax, pbx, rsz );
Merge201( p, pax, pbx, rsz );
}
std::swap(a, b); // swap ptrs
rsz <<= 2; // quadruple run size
}
return a; // return sorted array
}
void Merge3012( msptr *p, int *&pax, int *&pbx, size_t & rsz )
{
while(1)
{
if(*p[0].r <= *p[1].r)
{
if(*p[0].r <= *p[2].r)
{
*pbx++ = *p[0].r++; // run 0 smallest
if(p[0].r >= p[0].e) // if not end run continue
{
Merge212( p );
return;
}
}
else
{
if ( !Merge32( p, pbx ) ) return;
}
}
else
{
if(*p[1].r <= *p[2].r)
{
*pbx++ = *p[1].r++; // run 1 smallest
if(p[1].r >= p[1].e) // if not end run continue
{
Merge202( p );
return;
}
}
else
{
if ( !Merge32( p, pbx ) ) return;
}
}
}
}
// original
int * BottomUpMergeSortOrg(int a[], int b[], size_t n)
{
int *p0r; // ptr to run 0
int *p0e; // ptr to end run 0
int *p1r; // ptr to run 1
int *p1e; // ptr to end run 1
int *p2r; // ptr to run 2
int *p2e; // ptr to end run 2
int *p3r; // ptr to run 3
int *p3e; // ptr to end run 3
int *pax; // ptr to set of runs in a
int *pbx; // ptr for merged output to b
size_t rsz = 1; // run size
std::cout << "Org...." << std::endl;
if(n < 2)
return a;
if(n == 2){
if(a[0] > a[1])std::swap(a[0],a[1]);
return a;
}
if(n == 3){
if(a[0] > a[2])std::swap(a[0],a[2]);
if(a[0] > a[1])std::swap(a[0],a[1]);
if(a[1] > a[2])std::swap(a[1],a[2]);
return a;
}
while(rsz < n){
pbx = &b[0];
pax = &a[0];
while(pax < &a[n]){
p0e = rsz + (p0r = pax);
if(p0e >= &a[n]){
p0e = &a[n];
goto cpy10;}
p1e = rsz + (p1r = p0e);
if(p1e >= &a[n]){
p1e = &a[n];
goto mrg201;}
p2e = rsz + (p2r = p1e);
if(p2e >= &a[n]){
p2e = &a[n];
goto mrg3012;}
p3e = rsz + (p3r = p2e);
if(p3e >= &a[n])
p3e = &a[n];
// 4 way merge
while(1){
if(*p0r <= *p1r){
if(*p2r <= *p3r){
if(*p0r <= *p2r){
mrg40: *pbx++ = *p0r++; // run 0 smallest
if(p0r < p0e) // if not end run continue
continue;
goto mrg3123; // merge 1,2,3
} else {
mrg42: *pbx++ = *p2r++; // run 2 smallest
if(p2r < p2e) // if not end run continue
continue;
goto mrg3013; // merge 0,1,3
}
} else {
if(*p0r <= *p3r){
goto mrg40; // run 0 smallext
} else {
mrg43: *pbx++ = *p3r++; // run 3 smallest
if(p3r < p3e) // if not end run continue
continue;
goto mrg3012; // merge 0,1,2
}
}
} else {
if(*p2r <= *p3r){
if(*p1r <= *p2r){
mrg41: *pbx++ = *p1r++; // run 1 smallest
if(p1r < p1e) // if not end run continue
continue;
goto mrg3023; // merge 0,2,3
} else {
goto mrg42; // run 2 smallest
}
} else {
if(*p1r <= *p3r){
goto mrg41; // run 1 smallest
} else {
goto mrg43; // run 3 smallest
}
}
}
}
// 3 way merge
mrg3123: p0r = p1r;
p0e = p1e;
mrg3023: p1r = p2r;
p1e = p2e;
mrg3013: p2r = p3r;
p2e = p3e;
mrg3012: while(1){
if(*p0r <= *p1r){
if(*p0r <= *p2r){
*pbx++ = *p0r++; // run 0 smallest
if(p0r < p0e) // if not end run continue
continue;
goto mrg212; // merge 1,2
} else {
mrg32: *pbx++ = *p2r++; // run 2 smallest
if(p2r < p2e) // if not end run continue
continue;
goto mrg201; // merge 0,1
}
} else {
if(*p1r <= *p2r){
*pbx++ = *p1r++; // run 1 smallest
if(p1r < p1e) // if not end run continue
continue;
goto mrg202; // merge 0,2
} else {
goto mrg32; // run 2 smallest
}
}
}
// 2 way merge
mrg212: p0r = p1r;
p0e = p1e;
mrg202: p1r = p2r;
p1e = p2e;
mrg201: while(1){
if(*p0r <= *p1r){
*pbx++ = *p0r++; // run 0 smallest
if(p0r < p0e) // if not end run continue
continue;
goto cpy11;
} else {
*pbx++ = *p1r++; // run 1 smallest
if(p1r < p1e) // if not end run continue
continue;
goto cpy10;
}
}
// 1 way copy
cpy11: p0r = p1r;
p0e = p1e;
cpy10: while (1) {
*pbx++ = *p0r++; // copy element
if (p0r < p0e) // if not end of run continue
continue;
break;
}
pax += rsz << 2; // setup for next set of runs
}
std::swap(a, b); // swap ptrs
rsz <<= 2; // quadruple run size
}
return a; // return sorted array
}
int main()
{
int *source;
int *dest;
srand( (unsigned int) time( NULL ) );
const int count = 15000000;
double avg{ 0.0 };
for( int n = 0; n < 70; ++n )
{
source = new int[ count ];
dest = new int[ count ];
for( int n = 0; n < count; ++n )
{
source[ n ] = rand();
dest[ n ] = 0;
}
time_t s = clock();
#ifdef ORG
int * result = BottomUpMergeSortOrg( source, dest, count );
#else
int * result = BottomUpMergeSortAlt( source, dest, count );
#endif
time_t e = clock();
avg += ( e - s );
std::cout << "Time: " << ( e - s ) << " Avg: " << avg / ( double( n ) + 1.0 ) << std::endl;
int val = dest[ 0 ];
for( int n = 1; n < count; ++n )
{
if ( val > source[ n ] ) { std::cout << "Not sorted" << std::endl; break; }
val = source[ n ];
}
delete[] source;
delete[] dest;
}
return 0;
}
It is, as the original, a flat file (no header). It is not an attempt at high quality C++, just a re-read/refactor eliminating the use of goto.