Simplified version of bottom up merge sort that takes the temp array pointer (b) as a parameter:
Code:
// tsortbx.h - bottom up merge sort
#ifndef min
#define min(a,b) (((a) < (b)) ? (a) : (b))
#endif
template <class T>
T * MergeSort(T a[], T b[], const size_t n) {
for(size_t s = 1; s < n; s <<= 1){ // s = run size
size_t o = 0; // init output index
while(o < n){ // merge pairs of runs
size_t l = o; // update run indices
size_t le = min(l+s, n);
size_t r = le;
size_t re = min(r+s, n);
while(l < le && r < re)
b[o++] = (a[l] < a[r]) ? a[l++] : a[r++];
// copy remaining values
while (l < le) b[o++] = a[l++];
while (r < re) b[o++] = a[r++];
}
std::swap(a, b); // swap array ptrs
}
return a; // return sorted array
}