shellsort.js

/* Shell sort is basically an insertion sort
 * with variable gap (interval) between numbers
 * that it sorts in a given pass.  By beginning 
 * with large gaps between indexes, rough sorts 
 * are performed, making the final insertion sort 
 * (gap === 1) more efficient than usual.
 * Efficiency: O(n^1.5)
 */

function shellSort(arr, gap) {
  while (gap >= 1) {
    // for every item in the array
    for (var i = gap; i < arr.length; i++) {
      
      // store object at current index in a variable
      var currentItem = arr[i];
      
      // create a second index variable
      var j = i;
      
      /* shift forward previous elements in the array 
       * until the current object is less than or equal
       * to an index or we reached the beginning of 
       * the array and place it there */
      while (j >= gap && currentItem < arr[j - gap]) {
        //console.log("Shifting : " + arr[j], arr[j-1]);
        arr[j] = arr[j - gap];
        j -= gap;
      }
      
      /* element located at j is greater than
       * or equal to currentItem, so we can place
       * currentItem at j */
      arr[j] = currentItem;
    }
    
    // Halve gap, ensure the result is odd and repeat sort
    gap = Math.floor(gap / 2);
    if (gap % 2 === 0 && gap !== 0) gap++;
  }
  
  return arr;
}


var arr = [34,41,6,-1,23,614,0,3,0,1,55,14];
console.log(shellSort(arr, 5));