Insert is sorted much faster than shell sort

Question

I am reading a chapter on sorting in Sejuik's Algorithms. Along the way, I wrote 3 basic sorting algorithms: selecting, inserting, and sorting a shell. The book says that, despite the fact that all three have the quadratic complexity of the worst case, the shell type should be much faster than sorting the insert by random data. In the book, they get 600 times better productivity.

But I get the following factors (almost unchanged with increasing size of the array) on my laptop:

• selection: 5.5x
• insert: 1x
• shell: 1.8x!

The question that bothers me is , why is shell sorting almost twice as slow as inserting sorting ?!

I guess something is wrong with my shellsort implementation. But I almost copied it from a book:

class ShellSort extends Sort { //precalculate sequence: 1, 4, 13, 40, 121, 364, 1093, ... //(3^20 - 1)/2 is enough for any array I sort private static final int[] SEQUENCE = new int[20]; static { for(int i = 1; i <= SEQUENCE.length; i++) SEQUENCE[i - 1] = (int)(Math.pow(3, i) - 1) / 2; } public void sort(int[] a) { int length = a.length; int seqLen = SEQUENCE.length; int nth; int j; for(int seqi = seqLen - 1; seqi >= 0; seqi--) { if(SEQUENCE[seqi] < length / 3) { nth = SEQUENCE[seqi]; for(int n = 0; n < length; n+=nth) { j = n; while(j > 0 && a[j] < a[j - nth]) { exch(a, j, j-nth); j -= nth; } } } } } } 

The rest of the code is for those who want to run the test on their machine (doubling the JVM heated array size test does not have a significant effect on the results, so this simple test is good enough for N> ~ 200,000).

Main:

 int N = 500_000; Random rand = new Random(); int[] a = new int[N]; for(int i = 0; i < N; i++) a[i] = rand.nextInt(); //insertion sort int[] aCopy = Arrays.copyOf(a, a.length); long start = System.nanoTime(); new InsertionSort().sort(aCopy); System.out.println("insert:\t" + (System.nanoTime() - start)); //shell sort aCopy = Arrays.copyOf(a, a.length); start = System.nanoTime(); new ShellSort().sort(aCopy); System.out.println("shell:\t" + (System.nanoTime() - start)); 

InsertionSort and Sort classes:

 class InsertionSort extends Sort { public void sort(int[] a) { int length = a.length; int j; int x; for(int i = 1; i < length; i++) { j = i; x = a[i]; while(j > 0 && x < a[j-1]) { a[j] = a[--j]; } a[j] = x; } } } abstract class Sort { abstract public void sort(int[] a); protected static final void exch(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; } } 

Answer 1

Your implementation is broken and displays a sorted array only because the last step is 1, and the two inner loops perform basic insertion sorting when the step is 1. When the step is greater than 1, the two inner loops in your implementation do something other than step of sorting the array, so what you do is shuffle the array in all iterations of the outer loop, and then insert - sorts it in the last iteration of the outer loop. Of course, this will take longer than just pasting - sort it once.

Repeating your sequence, the correct shell sort implementation should look like this:

 public void sort( int[] a ) { int length = a.length; int stepIndex = 0; while ( stepIndex < SEQUENCE.length - 1 && SEQUENCE[ stepIndex ] < length / 3 ) { stepIndex++; } while ( stepIndex >= 0 ) { int step = SEQUENCE[ stepIndex-- ]; for ( int i = step; i < length; i++ ) { // DIFF: i++ instead of i+=step for ( int j = i; j >= step && a[ j ] < a[ j - step ]; j -= step ) { exch( a, j, j - step ); } } } } 

Two main differences between this implementation and yours:

• proper starting indices for two inner loops
• correct index increment for the middle loop (+1 instead of + step in your code)

Also check out http://algs4.cs.princeton.edu/21elementary/Shell.java.html for a good implementation and a good sequence of steps.

Answer 2

With a quick glance, you can see that the look of the shell looks slower with more cycles. Brute force, you can put system.out.println in the innermost loop to find out how many comparisons are made.

3 hinges shellsort

• for (int seqi = seqLen - 1; seqi> = 0; seqi -)
• for (int n = 0; n <length; n + = nth)
• while (j> 0 && a [j] <a [j - nth])

2 insertion loops

• for (int i = 1; i <length; i ++)
• while (j> 0 & x <a [j-1])

Answer 3

I believe caching will be the reason. Shell sort has a lot of (kinda) random accesses, so there are more cache misses. I believe that this will lead to poor performance when using new hardware. Insert sorting almost always works on the same memory areas, so it works better