Mergesort bottom-up

Question

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<size ; width*=2) {
        // iterating backwards as iterating forward 
        // does not work. mergeOutOfPlace is common 
        // for different merge algorithms. When iterating 
        // forward the left array has a bug
        int next=size-width, curr=size;
        for ( ; next>=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++]);
        }
    }

    // copy into original array
    for(int i=first, j=0; j<last-first; ++i, ++j) {
        arr[i] = tempArr[j];
    }

    delete[] l;
    delete[] r;
    delete[] tempArr;
}

Main

int main() {
    int size = 15, arr[] = {14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};

    print(arr, size);
    mergeSortBottomUp(arr, 0, size, size);
    print(arr, size);

    _getch();
    return 0;
}

Output

14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14

Answer 1

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

1. 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
2. Also in mergeSortBottomUp, create an auxiliary buffer capable to fit the entire input range.
3. If the integer from (1) is odd, copy the contents of the input range to the buffer.
4. 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)