// sorts array in place and returns an array of actions
function shellsort(arr) {
  var N = arr.length,
      actions = [],
      h = 1;

  while (h < N/3) h = 3*h + 1;

  actions.push({type: "parameter", val: h})
  while(h >= 1){
    for(var i = h; i < N; i++) {
      actions.push({type: "index", val: i});
      for(var j = i; j >= h && arr[j] < arr[j-h]; j -= h) {
        swap(arr, j, j-h);
        actions.push({type: "swap", i: j, j: j-h});
      }
    }
    h = Math.floor(h/3);
    actions.push({type: "parameter", val: h});
  }

  return actions;
}

function swap(arr, i, j) {
  var t = arr[i];
  arr[i] = arr[j];
  arr[j] = t;
}

// Node or browser?
if (typeof window === 'undefined') {
    module.exports = shellsort;

} else {
    window.shellsort = shellsort;
}