insertion.rb

# Insertion sort
def insertion_sort(a)
  1.upto(a.length - 1) do |i|
    x = a[i]
    j = i - 1

    while j >= 0 && a[j] > x
      a[j + 1] = a[j]
      j -= 1
    end
    
    a[j + 1] = x
  end
  return a
end