Sometimes "goto" is useful
Here is an example of a 4 way (no minheap) bottom up merge sort, which is about 15% faster than a 2 way merge sort and about as fast (sometimes a bit faster) than quick sort, on a processor with 16 registers, such as X86 in 64 bit mode, where the compiler optimization uses 8 of the registers for pointers to the current and end of runs. Trying to remove the goto's in this case would duplicate code and make it more complex. To implement this in Java, which doesn't have goto (but does reserve it), I had to switch to a top down merge sort, which is a bit slower, somewhat defeating the purpose of a 4 way merge sort (for performance).
One general reason for using goto is when there are multiple paths leading to common code, and this is an example of that.
Code:
int * BottomUpMergeSort(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
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
}