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 }
