How can I speed up my shell sort?

Question

I'm trying to implement a bunch of sorting algorithms in JavaScript, and I can't figure out why my shell sort is so slow. It's 6x slower than my merge sort, and only slightly faster than my insertion sort. I've seen another implementation online, but I'm more focused on making it clear and readable (as I have a blog for noobs) and the faster implementation is too concise for my purposes. Any thoughts on how I can keep the general plan but get it moving faster? I tried using Marcin Ciura's gap sequence [701, 301, 132, 57, 23, 10, 4, 1], but it was slightly slower. I'm not sure what's the biggest factor slowing down my sort.

 var shellSort = function( list ) {
 var gapSize = Math.floor( list.length / 2 );
 while( gapSize > 0 ) {
 _shellInsertionSort( list, gapSize );
 gapSize = Math.floor( gapSize / 2 );
 }
 return list;
 };
 function _shellInsertionSort( list, gapSize ) {
 var temp, i, j;
 for( i = gapSize; i < list.length; i += gapSize ) {
 j = i;
 while( j > 0 && list[ j - gapSize ] > list[j] ) {
 temp = list[j];
 list[j] = list[ j - gapSize ];
 list[ j - gapSize ] = temp;
 j -= gapSize;
 }
 }
 };

My tests:

 var testSpeed = function( testSize, rounds ) {
 var testArrays = [],
 algorithms = Array.prototype.slice.call( arguments, 2 ),
 results = [],
 i, j;
 for( i = 0; i < rounds; i++ ) {
 testArrays[i] = [];
 for( j = 0; j < testSize; j++ ) {
 testArrays[i].push( Math.ceil( Math.random() * testSize ));
 }
 }
 for( i = 0; i < algorithms.length; i++ ) {
 for( j = 0; j < rounds; j++ ) {
 if( !results[i] ) {
 results[i] = [];
 }
 results[i].push( testAlgorithm( algorithms[i], testArrays[j] ));
 }
 }
 return results;
 };
 var testAlgorithm = function( algorithm, set ) {
 var clone = set.slice(),
 start = new Date().getTime(),
 end;
 algorithm( clone );
 end = new Date().getTime();
 return end - start;
 };

• David Harkness: The while test should be j >= gapSize to keep from checking negative indices with j - gapSize, but that should barely make a dent in the speed.
• David Harkness: And the psuedocode on the Wikipedia page increments i by 1 rather than gapSize in the outer for loop. While that means more iterations, perhaps it people forms better by sorting more large gaps.

Answer 1

@David Harkness sent my search in the right direction. As it is, the insertion sort portion is only going through one round for each gap, rather than walking up each round, so it's not actually going for more than one round, and most of the sorting isn't done until the gap is 1. When I start fixing problem, it just started getting more convoluted, so I ditched my original approach and followed the pseudocode on wikidepia. Now, it's quite snappy:

var shellSort = function( list ) {
 var gap = Math.floor( list.length / 2 );
 while( gap > 0 ) {
 for( i = gap; i < list.length; i++ ) {
 temp = list[i];
 for( j = i; j >= gap && list[j - gap] > temp; j -= gap ) {
 list[j] = list[j - gap];
 }
 list[j] = temp;
 }
 gap = Math.floor( gap / 2 );
 }
 return list;
 };