let gaps = getBestGap(arr.length)

function getBestGap (len) {
  let gap = [], j = 0;
  for (let i = 0; true; i++) {
    if (gap.length === 0 || len > gap[j - 1]) {
      gap.push(9 * Math.pow(4, i) - 9 * Math.pow(2, i) + 1)
      j++
    } else {
      break
    }
    if (len > gap[j - 1]) {
      gap.push(Math.pow(2, i + 2) * (Math.pow(2, i + 2) - 3) + 1)
      j++
    } else {
      break
    }
  }
  gap.pop()
  return gap
}

for (let gapsIndex = gaps.length - 1; gapsIndex >= 0; gapsIndex--) {
  let gap = gaps[gapsIndex]
  for (let k = 0; k < gap; k++) {
    for (let i = gap; i < arr.length; i += gap) {
      let j = i
      while (arr[j] < arr[j - gap] && j > 0) {
        arr[j] = arr[j] ^ arr[j - gap]
        arr[j - gap] = arr[j - gap] ^ arr[j]
        arr[j] = arr[j] ^ arr[j - gap]
        j -= gap
      }
    }
  }
}

总结

参照维基百科上的思路，把数组想象成表格，每次分别对列排序。然后再调整步长重复操作。