I'm merge sorting int arrays of length 10,000 to 75,000. I am getting strange sort times. Why might this be?

I am doing an assignment for my algorithms class and I have to demonstrate that internal merge sort has a time complexity of O(nlogn). To do this I made arrays ranging in length from 10,000 elements long to 75,000 elements long. Then I load the array with random numbers < 10,000, and output the array length to the console with how long it took to sort.

The strange result is that some take ~15 milliseconds give or take and then others take 0 milliseconds, even if the array is tens of thousands of integers longer. Any idea of why this may be? I can upload a screen shot of my output, but someone needs to approve it because I don't have enough "reputation". I have checked the arrays. They do appear to be sorted after calling the mergeSort() method.

 public static void main(String[] args){
    int[] dataLength = {10_000, 15_000, 20_000, 25_000, 30_000, 35_000, 40_000, 45_000, 50_000, 
                        55_000, 60_000, 65_000, 70_000, 75_000};
  //        internal merge sort
    for (int i = 0; i < dataLength.length; i++) {
        int[] input = new int[dataLength[i]];

        for (int j = 0; j < input.length; j++) {
            input[j] = random.nextInt(10000);
        }

        long startTime = System.currentTimeMillis();
        mergeSort(input, 0, input.length);
        long endTime = System.currentTimeMillis();

        System.out.println("Length of array is: " + input.length  + ". The sorted array: "
                + Arrays.toString(input));
        System.out.println("Internal sort with " + dataLength[i] + " items took: " +
                (endTime - startTime) + " milliseconds");
    }
 }

 public static void mergeSort(int[] input, int start, int end) {
    if (end - start < 2) {
        return;
    }

    int mid = (start + end) / 2;
    mergeSort(input, start, mid);
    mergeSort(input, mid, end);
    merge(input, start, mid, end);
    return;
}

public static void merge(int[] input, int start, int mid, int end) {
    if (input[mid - 1] <= input[mid]) {
        return;
    }
 //        index of "left" array
    int i = start;
 //        index of "right" array
    int j = mid;
    int tempIndex = 0;
    int[] temp = new int[end - start];

    while (i < mid && j < end) {
        temp[tempIndex++] = input[i] <= input[j] ? input[i++] : input[j++];
    }
 //        optimizes the merge. If there are elements in the left array we just copy them back
 //        into the input array instead of merging them with the temp array first
    System.arraycopy(input, i, input, start + tempIndex, mid - i);
    System.arraycopy(temp, 0, input, start, tempIndex);
    return;
}

1 answer

  • answered 2019-12-14 18:00 theChoosyBeggar

    Thanks for the help everyone. I liked the comment about using nanoTime instead of milliseconds. When dealing with numbers this small milliseconds would be too large. Also the JMH idea also sounds smart even though I'm sure the professor doesn't actually expect us to use outside software to test the program. Any other insights would be appreciated. It's very interesting.