# 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;
}
``````