Shell sort is a generalization of algorithms like bubble or insertion sort. Shell sort breaks down a list into a number of sublists. Key thing is choosing a sublist and having a gap between elements in the same sublist.

Ruby implementation:

def shell_sort(array)
  n = array.length
  return -1 if n.zero?

  while n / 2 != 0
    n /= 2

    0.step(array.length) do |i|
      (i + n).step(array.length - 1, n) do |g|
        temp = array[g]
        j = g
        while j >= i
          break if array[j] >= array[j - n]
          array[j] = array[j - n]
          j -= n
        end
        array[j] = temp
      end
    end
  end
  array
end

array = [20, 50, 1, 49, 22, 70, 1, 35, 32]
shell_sort(array)
puts array.inspect
#=> [1, 1, 20, 22, 32, 35, 49, 50, 70]