Optimizing Mergesort in Java for O(Nlog(N))

Question

A partner and I are attempting to program Mergesort in Java. We have completed the algorithm, and it functions properly. However, in testing the algorithm for a variety of inputs, we noticed that it does not perform within the bound of O(Nlog(N)). We have been attempting to optimize the algorithm further and would appreciate any and all suggestions. The only requirement is that we cannot change the method headers. Our Java code is listed below:

    /**
 * MergeSort algorithm driver.
 * 
 * @param arr - input ArrayList of objects
 */
public static <T extends Comparable<? super T>> void mergesort(
        ArrayList<T> arr)
{
    // Pre-allocation of a temporary ArrayList
    // for merge space.
    ArrayList<T> temp = new ArrayList<T>(arr.size());
    temp.addAll(arr);

    // Call the recursive mergesort method.
    mergesort(arr, temp, 0, arr.size() - 1);
}

/**
 * Main mergeSort method. Makes recursive calls. 
 * 
 * @param arr - input ArrayList of objects
 * @param temp - temporary ArrayList to hold the merged result 
 * @param left - start of the subarray 
 * @param right - end of the subarray
 */
private static <T extends Comparable<? super T>> void mergesort(
        ArrayList<T> arr, ArrayList<T> temp, int left, int right)
{

    // If the size of the subcollection is less than a given threshold,
    // then perform an insertion sort rather than a mergesort.
    //if ((right - left) < threshold)
    //  insertionsort(arr, left, right);


    // If the size of the subcollection was not less than our threshold and 
    // the left end is less than the right end of subcollection, then we are 
    // done performing the sort.
    if(left < right)
    {
        int center = (left + right) / 2;
        mergesort(arr, temp, left, center);
        mergesort(arr, temp, center + 1, right);
        merge(arr, temp, left, right);
    }
}

/**
 * Internal method for merging two sorted subarrays. This is to be used with the 
 * mergesort algorithm.
 * 
 * @param arr - input ArrayList of objects
 * @param temp - temporary ArrayList in  which the result with be placed
 * @param currentLeft - start of the subarray 
 * @param rightEnd - end of the subarray
 */
private static <T extends Comparable<? super T>> void merge(
        ArrayList<T> arr, ArrayList<T> temp, int leftStart, int rightEnd)
{
    int currentLeft = leftStart;
    int leftEnd = (currentLeft + rightEnd) / 2;
    int rightStart = leftEnd + 1;


    // Main loop - compares the value in the left position
    // to the value in the right position.  
    while( currentLeft <= leftEnd &&  rightStart <= rightEnd)
    {
        // If the value in the left position is less than the right, 
        // place the left position value in the temporary collections.
        if(arr.get(currentLeft).compareTo(arr.get(rightStart)) <= 0)
        {
            temp.add(arr.get(currentLeft++));

        }


        // Otherwise, place the value in the rightStart position in
        // the temporary collection.
        else
        {
            temp.add(arr.get(rightStart++));

        }
    }

    // Copy the remaining left half.
    while( currentLeft <= leftEnd )
        temp.add(arr.get(currentLeft++));


    // Copy the remaining right half.
    while( rightStart <= rightEnd )
        temp.add(arr.get(rightStart++));


    // Loop through the temporary collection and for each element
    // currently in the collection, copy the contents back into the
    // original collection.
    for (int i = leftStart, count = 0; i <= rightEnd; i++, count++)
        arr.set(i, temp.get(count));

    // After the above operation has been completed for this particular
    // call, clear the temporary collection.
    temp.clear();

}

Answer 1

Converting my comment to an answer -

To say that an algorithm has runtime O(n log n) does not mean that the runtime of the function will exactly match a plot of the function f(n) = n log n. Instead, it means that the runtime of the function grows at the same rate as the runtime of the function n log n. Therefore, for large n, if you double the size of the input, the runtime should slightly more than double.

The fact that you mentioned that your function's runtime is roughly three times the value of n log n is actually strong evidence that you have an O(n log n) runtime - your function has runtime roughly 3n log n, which means that its runtime is O(n log n), since big-O ignores constant factors. To be more mathematically accurate - the constant you have probably isn't exactly 3, since the value of n is dimensionless (it measures a quantity), while the runtime is in seconds, so there's some unit conversion going on here.

Hope this helps!