I’m doing an experiment to compare how Thomas Hibbard’s shell sort (gap size = 2^k-1) and Donald Shell’s shell sort (n/2^k) perform on the same array. When the size of the array is from 10 to 1000, Hibbard is performing better than shell. But when the size reaches 10000 or higher, shell sort is faster than Hibbard.
According to big O notation, Hibbard is O(N^1.5), Shell is O(N^2), which makes me think that Hibbard should have greater improvements over Shell as the size of the data set increases. Can anybody tell me why my results might not be as expected?
I understand that O notation is worst case complexity, but it seems that the performance should align better to the notation.
Here is my code written in JAVA: (note: unsortedArray is declared and initialized earlier)
{
int temp;
int[] sortedArray = unsortedArray.clone();
printArray();
int k = (int)(Math.log(sortedArray.length)/Math.log(2));
int gap = (int)(Math.pow(2,k)-1);
int count = 0;
long endTime;
long startTime = System.nanoTime();
while (gap > 0)
{
for (int g = 0; g < gap; g++)
{
for (int d = g + gap; d < sortedArray.length; d = d + gap)
{
for (int i = d; i - gap >= 0; i = i - gap)
{
if (sortedArray[i - gap] <= (sortedArray[i]) )
{
break;
}
count++;
temp = sortedArray[i];
sortedArray[i] = sortedArray [i-gap];
sortedArray[i-gap] = temp;
}
}
}
k = k -1;
gap = (int)(Math.pow(2,k)-1);
}
endTime = System.nanoTime();
System.out.println("The total time for hibbard sort is" + (endTime-startTime));
System.out.println("the number of swaps for hibbard sort is" + count);
}