Why is recursive merge sort function displaying O(

Question

I have tried implementing a merge sort recursively, and unfortunately, it seems to be displaying O(n^2) complexity rather than the desired O(nlogn). Here is the code, first I call a driver method(creating the temp array here so it doesn't need to reinitialize for every recursive call):

public static <T> void mergesort(ArrayList<T> list, Comparator<? super T> comparator) {

        // Create and initialize a temporary ArrayList to be passed through the
        // recursive method.
        ArrayList<T> temp = new ArrayList<T>();
        for (int i = 0; i < list.size(); i++) {
            temp.add(null);
        }
        mergeSortRecursive(list,temp, 0, list.size()-1, comparator);

    }

Once all the driver business is handled mergeSortRecusive is called(I switch to insertion sort once the subarrays reach a certain size. In this case INSERTTHRESHOLD is set to 10):

private static <T> void mergeSortRecursive (ArrayList<T> list, ArrayList<T> temp, int left, int right,  Comparator<? super T> comparator) {
        // If ArrayList size is less than the set threshold call the insertSort
        // method and return results instead continuing to call the recursive method.
        if(right - left < INSERTTHRESHOLD) {
        insertionSort(list, left, right, comparator);
        }

        // Find mid point in ArrayList biased on size of array.
        int mid = (left + right) / 2;

        // Recursively call the mergeSortRecursive method passing the first half of the
        // ArrayList.
        mergeSortRecursive(list,temp, left, mid, comparator);
        // Recursively call the mergeSortRecursive method passing the second half of the
        // ArrayList.
        mergeSortRecursive(list,temp, mid+1, right, comparator);

        // Merge the two half array lists back together and return the results.
        merge(list,temp, left, mid+1, right, comparator);


    }

Lastly, once everything is nice and split up the merge function is called to bring it all back together:

private static <T> void merge (ArrayList<T> list, ArrayList<T> temp, int start, int mid, int end, Comparator<? super T> comparator) {

        int i1 = start, i2 = mid;
        int index = start;
        // Loop through each Array list together.
        while (i1 < mid && i2 < end+1) {
            // If the item in the first ArrayList is smaller than the second
            // add that item to the temporary list and increment the index
            // of the first iterator.
            if(comparator.compare(list.get(i1), list.get(i2)) < 0) {
                temp.set(index, list.get(i1));
                index++;
                i1++;
            }
            // If the item in the first ArrayList is not smaller than the second
            // add the second ArrayList item to the temporary list and increment the index
            // of the second iterator.

            else {
                temp.set(index, list.get(i2));
                index++;
                i2++;
            }
        }

        // Add all remaining items from second ArrayList.
        while(i2 < end+1) {
            temp.set(index, list.get(i2));
            index++;
            i2++;
        }
        // Add all remaining items from first ArrayList.
        while(i1 < mid) {
            temp.set(index, list.get(i1));
            index++;
            i1++;
        }

        //Replace the order of the list with the temporary list.
        for (int i = start; i <end+1 ; i++) {
            list.set(i,temp.get(i));
        }
    }

Here's the time graph:

Here's the average time over n^2:

here's the time over n*log(n):

So why is taking this thing so long?

Answer 1

Could you test this example code on your system? It's an optimized top down merge sort that operates on int (primitive). This example is sorting 10,000,000 ints, in about 1.2 seconds. For your example, I'm wondering about overhead of all those set calls (do these release and allocate memory?), and the overhead of an arraylist (array of pointers to objects).

package jsorttd;
import java.util.Random;

public class jsorttd {
    static void MergeSort(int[] a)          // entry function
    {
        if(a.length < 2)                    // if size < 2 return
            return;
        int[] b = new int[a.length];
        MergeSortAtoA(a, b, 0, a.length);
    }

    static void MergeSortAtoA(int[] a, int[] b, int ll, int ee)
    {
        if(ee - ll > 1) {
            int rr = (ll + ee)>>1;          // midpoint, start of right half
            MergeSortAtoB(a, b, ll, rr);
            MergeSortAtoB(a, b, rr, ee);
            Merge(b, a, ll, rr, ee);        // merge b to a
        }
    }

    static void MergeSortAtoB(int[] a, int[] b, int ll, int ee)
    {
        if(ee - ll > 1) {
            int rr = (ll + ee)>>1;          // midpoint, start of right half
            MergeSortAtoA(a, b, ll, rr);
            MergeSortAtoA(a, b, rr, ee);
            Merge(a, b, ll, rr, ee);        // merge a to b
        } else if((ee - ll) == 1) {         // if just one element
            b[ll] = a[ll];                  //   copy a to b
        }
    }

    static void Merge(int[] a, int[] b, int ll, int rr, int ee) {
        int o = ll;                         // b[]       index
        int l = ll;                         // a[] left  index
        int r = rr;                         // a[] right index
        while(true){                        // merge data
            if(a[l] <= a[r]){               // if a[l] <= a[r]
                b[o++] = a[l++];            //   copy a[l]
                if(l < rr)                  //   if not end of left run
                    continue;               //     continue (back to while)
                do                          //   else copy rest of right run
                    b[o++] = a[r++];
                while(r < ee);
                break;                      //     and return
            } else {                        // else a[l] > a[r]
                b[o++] = a[r++];            //   copy a[r]
                if(r < ee)                  //   if not end of right run
                    continue;               //     continue (back to while)
                do                          //   else copy rest of left run
                    b[o++] = a[l++];
                while(l < rr);
                break;                      //     and return
            }
        }
    }

    public static void main(String[] args) {
        int[] a = new int[10000000];
        Random r = new Random();
        for(int i = 0; i < a.length; i++)
            a[i] = r.nextInt();
        long bgn, end;
        bgn = System.currentTimeMillis();
        MergeSort(a);
        end = System.currentTimeMillis();
        for(int i = 1; i < a.length; i++){
            if(a[i-1] > a[i]){
                System.out.println("failed");
                break;
            }
        }
        System.out.println("milliseconds " + (end-bgn));
     }
}