Shell Sort

pseudocode

shellSort(a):
  for gap = floor(n/2) down to 1 (gap /= 2):
    for i = gap to n-1:
      j = i
      while j >= gap and a[j-gap] > a[j]:
        swap a[j-gap], a[j]
        j = j - gap // step backward by gap