Thread: minimalist bottom up merge sort

Code:

typedef vector<int> LIST; // LIST can be a vector of any comparable type

static LIST merge_sort(LIST &linp)
{
size_t i, width;

    LIST lout(linp.size()); // second list for output

    for(width = 1; width < linp.size(); width *= 2){ /* merge pass */
        for(i = 0; i < linp.size(); i += 2 * width){ /* merge sublists */
            merge_pair(lout, linp, i, min(i+width, linp.size()), min(i+2*width, linp.size()));
        }
        linp.swap(lout);    // swap lists (if optimized would swap ptrs)
    }
    return(linp);           // return sorted list
}   

static void merge_pair(LIST &lout, LIST &linp, size_t ileft, size_t iright, size_t iend)
{
size_t il = ileft;
size_t ir = iright;

/*  merge a pair of sublists */
 
    for (size_t iout = ileft; iout < iend; iout++){
        if (il < iright && (ir >= iend || linp[il] <= linp[ir]))
            lout[iout] = linp[il++];
        else
            lout[iout] = linp[ir++];
    }
}