I'm trying to analyse the run time of my implementation of merge and insertion sort. I'm noticing a weird trend and I wasn't able to find anyone with the same problem through googling, but I'm probably using the wrong terms.
The number of times the sorting algorithms run, seem inversely related to the amount of time taken for the algorithm to complete. Sample shown below for insertion sort.
4213,2104,8195,9441,4823,925,980,964,911,491,470,482,481... (it settles on ~490ms)
And similar behaviour with merge sort, but merge settles on ~95ms.
I have no idea why this is happening, I'm generating a random array every time... even if it wasn't random shouldn't it just take exactly the same time every time (or close)? why does it converge on a smaller value?
Just looking for anyone who might know why this is happening because it seems really strange to me... I'm assuming it's something Java is doing behind the scenes maybe? Any suggestions/tips appreciated!
All the code I am running is posted below. With the test code shown first.
public static void tests(int noTests, int arraySize){
//set up the running totals of the time taken by insertion and merge
double insertSum = 0;
double mergeSum = 0;
for(int i = 0; i < noTests; i++){
//generate an array of random integers
Integer[] randInput = generateRandomArray(arraySize);
//start the clock for insertion
final long insertionStart = System.nanoTime();
//sort it
insertionSort(randInput);
//stop the clock for insertion
final long insertionFinish = System.nanoTime();
System.out.println("Time taken for insertion: " + (insertionFinish - insertionStart)/1000 + " ms");
//add it to the running total
insertSum += (insertionFinish - insertionStart)/1000;
//likewise for merge
final long mergeStart = System.nanoTime();
mergeSort(randInput);
final long mergeFinish = System.nanoTime();
System.out.println("Time taken for merge: " + (mergeFinish - mergeStart)/1000 + " ms");
mergeSum += (mergeFinish - mergeStart)/1000;
}
//Get the average by diving by the number of times it ran
System.out.println("-------------------------------------------------------");
System.out.println("Insert average: " + insertSum/noTests);
System.out.println("Merge average: " + mergeSum/noTests);
}
//Generate an array of random Integers
public static Integer[] generateRandomArray(int n){
Integer[] arr = new Integer[n];
for(int i = 0; i < n; i++){
arr[i] = (int) Math.floor(Math.random()*100);
}
return arr;
}
public static <T extends Comparable<T>> T[] insertionSort(T[] a){
for(int i = 1; i < a.length; i++){
int j = i-1;
T key = a[i];
while(j >= 0 && a[j].compareTo(key) > 0){
a[j+1] = a[j];
j = j-1;
}
a[j+1] = key;
}
return a;
}
@SuppressWarnings("rawtypes")
public static Comparable[] mergeSort(Comparable[] input){
if(input.length<=1){
return input;
}
int middle = Math.floorDiv(input.length, 2);
Comparable a[] = new Comparable[middle];
for(int i = 0; i < middle; i++){
a[i] = input[i];
}
Comparable b[] = new Comparable[input.length - middle];
for(int i = middle; i < input.length; i++){
b[i-middle] = input[i];
}
mergeSort(a);
mergeSort(b);
merge(input, a, b);
return input;
}
@SuppressWarnings({ "rawtypes", "unchecked" })
public static void merge(Comparable[] input, Comparable[] a, Comparable[] b){
int inputIndex = 0;
int aIndex = 0;
int bIndex = 0;
while(aIndex < a.length && bIndex < b.length){
if(aIndex < a.length & a[aIndex].compareTo(b[bIndex]) < 0){
input[inputIndex] = a[aIndex];
aIndex++;
} else{
input[inputIndex] = b[bIndex];
bIndex++;
}
inputIndex++;
}
}
Example output:
Time taken for insertion: 4266 ms
Time taken for merge: 643 ms
Time taken for insertion: 2127 ms
Time taken for merge: 199 ms
Time taken for insertion: 8001 ms
Time taken for merge: 201 ms
Time taken for insertion: 9568 ms
Time taken for merge: 157 ms
Time taken for insertion: 9614 ms
Time taken for merge: 158 ms
Time taken for insertion: 495 ms
Time taken for merge: 125 ms
Time taken for insertion: 485 ms
Time taken for merge: 141 ms
Time taken for insertion: 508 ms
Time taken for merge: 517 ms
Time taken for insertion: 484 ms
Time taken for merge: 804 ms
Time taken for insertion: 484 ms
Time taken for merge: 796 ms
-------------------------------------------------------
Insert average: 3603.2
Merge average: 374.1
Thanks!
