Mergesort bottom-up

I am looking for suggestions on how to improve my mergesort. My teacher explained the recursive mergesort and left the bottomUp one as an assignment. I have implemented it but find it too messy. I thought the implementation would be more simple.

How can I make it simpler and quicker?

MergeSort

void mergeSortBottomUp(int *arr, int first, int last, int size) {
    if (size == 0) return;
    // width determines the length of the 2 arrays, the contiguous
    // arrays which are sent to the mergeOutOfPlace function.
    int width=2;
    // we select arrays with length = power of 2.
    for ( ; width=0; curr=next, next-=width) {
            int mid = (curr+next)/2;
            mergeOutOfPlace(arr, next, mid, curr);
        }
        // whenever array of length = pow2 is not selectable
        // we select varied length array, which is always near
        // the end of iteration
        if (curr>=2) {
            mergeOutOfPlace(arr, 0, (size%(width>>1)), curr);
        }
    }
    // if array not power of 2
    if ( (size%(width>>1)) != 0 )
        mergeOutOfPlace(arr, 0, size%(width>>1), size);
    // if array power of 2
    else mergeOutOfPlace(arr, 0, size/2, size);
}

Merge

```
void mergeOutOfPlace(int *arr, int first, int mid, int last) {
// Merges two contigous sub-arrays and sorts them out-of-place
// Condition Required: Sub-arrays must be sorted individually
int *l = new int [mid-first];
int *r = new int [last-mid];
int *tempArr = new int [last-first];

// copying into new arrays
for (int i=0, j=first; i<mid-first; ++i, ++j) {
l[i] = arr[j];
}
for (int i=0, j=mid; i<last-mid; ++i, ++j) {
r[i] = arr[j];
}

// merge
for(int i=0, j=0, k=0; k<last-first; ++k) {
if (i == mid-first) {
tempArr[k] = r[j++];
}
else if (j == last-mid) {
tempArr[k] = l[i++];
}
else {
(l[i] < r[j]) ? (tempArr[k] = l[i++]) : (temp[k] = r[j++]

What comes to "quicker", you could improve your mergeOutOfPlace in the following way:

• In mergeSortBottomUp, find out how many merge passes over the input range you need to do in order to bring order to that very range

• Also in mergeSortBottomUp, create an auxiliary buffer capable to fit the entire input range.

• If the integer from (1) is odd, copy the contents of the input range to the buffer.

• Begin your first merge pass: merge element 1 with element 2, 3 with 4, 5 with 6, and so on. Here you could use std::merge: pass it both the input array and the buffer array. When you get to the last element in the current merge pass, swap the roles of your two arrays: the source array becomes the target array, the target array becomes the source array.

(So, if the integer from (1) is odd, in the initial merge pass you treat the buffer as the source and put the merged runs into the actual input array; after everything is merged, your stuff will magically end up in the input array. Conversely, if the integer from (1) is even, just treat initially the input array as the source array in the first merge pass; sorted range after the last merge will appear in the input array.)

That way, you get:

• More performance

• Less code (since you could use std::merge)

StackExchange Code Review Q#84544, answer score: 2