Thread: merge sort - top down versus bottom up

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
}