How to determine the possible running time of merge sort on an array of ints?

Question

I am testing the running times of some of my sorting algorithms, I tested this algorithm on an array of size 1,280,000 and got a running time of approximately 0.246 seconds. I am now trying to figure out the theoretical running time of my algorithm on an array of double the size(2,560,000). I am trying to figure out how to calculate the the running time based on the big-O of merge sort which is nlog(n). I plugged in .246 into the nlogn algorithm but came up with a negative number. Google and other stack overflow questions did not exactly help. My mergeSort works correctly, but I attached the code for it below. Any help is appreciated, thanks in advance!

/**
 * This is another sorting algorithm where the data array is first split
 * into two, then recursively sorted, at each recursive level the method
 * will merge the current two variables together, and by the time the method
 * reaches the root call the array will be sorted.
 * @param data: The array that needs to be sorted.
 * @param first: The starting index of the sort.
 * @param n : The ending index of the sort.
 */
public static void mergeSort(int[] data, int first, int n) {

    if (data.length < 2) {
        return;
    }
    int n1;//first element of first half
    int n2;//first element of the second half
    if (n > 1) {
        //figure out the size of the array
        n1 = n / 2;
        n2 = n - n1;

        mergeSort(data, first, n1);
        mergeSort(data, first + n1, n2);

        //now merge the two halves
        merge(data, first, n1, n2);
    }

}

private static void merge(int[] data, int first, int n1, int n2) {
    int[] temp = new int[n1 + n2];
    int copied = 0;
    int copied1 = 0;
    int copied2 = 0;
    int i;

    while ((copied1 < n1) && (copied2 < n2)) {
        if (data[first + copied1] < data[first + n1 + copied2]) {
            temp[copied++] = data[first + (copied1++)];
        } else {
            temp[copied++] = data[first + n1 + (copied2++)];
        }
    }
    //make sure copied1 is completely transferred over
    while (copied1 < n1) {
        temp[copied++] = data[first + (copied1++)];
    }
    //copy temp into data to complete the process
    for (i = 0; i < copied; i++) {
        data[first + i] = temp[i];
    }

}

Answer 1

Your test size is simply to small.

You need to repeat your experiment a number of times and with a lot of different sizes so you can make a plot of different time consumption plots.

The reason: on a physical processor, a machine uses cache: a fast memory so the processor is optimally used. It takes sometime before a program is fully loaded into the cache.

This means that the first time you run a program, it takes more time because part of the time is wasted on loading the program. This is called a cold start. The second time, one can benefit from the work earlier performed by the previous run. This is called a hot start.

Furthermore running times tend to depend on external factors as well. Say you run the program, but at the same time something happens on the network or you insert a USB device. In that case the operating system will suspend execution, and first do some bookkeeping for the event. Bookkeeping can run into milliseconds and thus have a significant impact on a single run.

Furthermore you need to try different arrays. Sorted arrays are typically sorted faster than unsorted arrays. This is because many merge implementations use swapping (to boost performance) and thus perform less swaps.

To conculde: you should use different arrays, different sizes, and repeat the experiment often enough to average out aspects like caching.

Given you did this, you can determine the running time as follows. Since the time complexity is O(n log n), this means the function takes the form:

a*n log n+b*n+c*log n+d

You can plug this formula into a Vandermonde matrix for the Least squares method:

[  1    log(n_1)    n_1    n_1*log(n_1)  ]                 [ t_1 ]
[  1    log(n_2)    n_2    n_1*log(n_2)  ]      [ d ]      [ t_2 ]
[  1    log(n_3)    n_3    n_1*log(n_3)  ]      [ c ]      [ t_3 ]
[  1    log(n_4)    n_4    n_1*log(n_4)  ]   x  [ b ]  =   [ t_4 ]
[  1    log(n_5)    n_5    n_1*log(n_5)  ]      [ a ]      [ t_5 ]
[  1      ...       ...        ...       ]                 [ ... ]
[  1    log(n_m)    n_m    n_1*log(n_m)  ]                 [ t_m ]

Or in matrix notation:

X * w = t

With n_i the array size for experiment i and t_i the time it took to sort this array.

You can then determine the constants by calculating:

w = (X^T*X)^-1*X*t

You can do this for instance using GNU/Octave.

You then can derive a, b, c and d by using the method of the least squares. This should give a good approximation for the timings.

In case they differ too much, something is wrong with your implementation. In case a is (near to) zero, it is likely that your algorithm behaves sub O(n log n) and in case the function doesn't keep up with the datapoints, the behavior is stronger (thus O(n^2))

Answer 2

In "theory" merge sort is an algorithm with complexity of O(n.log(n)).
This a fact we both know, but: in reality many factors play against and for us. i.e. Memory limits, CPU overloads and in your case Java Heap.

Let's assume you have ran your code on a machine with no boundaries:

=

0.246 = alpha * n * log(n)
where n=1,280,000 and alpha is our machine process factor

0.246 = alpha * 1.28E+6 * log(1.28E6) --> alpha = 0.246/(1.28E6*log(1.28E6)) --> alpha = 3.14689524e-8

and now let's replace numbers with calculated alpha and n=2,560,000:

estimate = 3.14689524e-8 * 2.56E6 * log(2.56E6) --> estimate = 0.51625113199

so it take about 0.516 seconds.

Note: this only works when you have unlimited resources and no background processes.