I am testing the run times of insertion sort using iterative and recursive functions.
However, my results are showing that the iterative version is taking longer to sort than the recursive version. Is this correct?
// Used to determine how long a sort took
private long startTime, stopTime;
public int[] recursiveSort(int[] list){
// Start the clock
this.startTime = System.nanoTime();
int n = list.length;
insertionSortRecursive(list, n);
// Stop the clock
this.stopTime = System.nanoTime();
return list;
}
public void insertionSortRecursive(int[] arr, int n){
// Base case
if (n <= 1)
return;
// Sort first n-1 elements
insertionSortRecursive( arr, n - 1 );
// Insert last element at its correct position in sorted array.
int last = arr[n - 1];
int j = n - 2;
// Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position.
while (j >= 0 && arr[j] > last){
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = last;
}
My iterative version is below. I have run a test 50 of random array of size 3000, and for all of them, the time it took to sort the array recursively took less time than iteratively.
public int[] iterativeSort(int[] list){
// Start the clock
this.startTime = System.nanoTime();
int n = list.length;
for (int i = 1; i < n; ++i){
int key = list[i];
int j = i-1;
/* Move elements of list[0..i-1], that are greater than key, to one position ahead of their current position */
while (j >= 0 && list[j] > key){
list[j + 1] = list[j];
j = j - 1;
}
list[j + 1] = key;
}
// Stop the clock
this.stopTime = System.nanoTime();
return list;
}