Insertion sort

insertion_sort.rb

# O(n^2)
def insertion_sort arr
i = 0
j = 0
  for i in 1...(arr.length) do
    key = arr[i]
    
    j = i - 1
    while j >= 0 and key < arr[j] do
       arr[j + 1] = arr[j] 
       j -= 1
    end 
     arr[j + 1] = key
  end
  arr
end

arra = [1,6,0,5,12]
puts insertion_sort(arra)
# => 0 1 5 6 12