insertion_sort.rb

def insertion_sort(seq)    
    (1..seq.size - 1).each do |i|
        key = seq[i]
        left = i - 1

        while left >= 0 and seq[left] > key
            seq[left + 1] = seq[left]
            seq[left] = key
            left -= 1
        end
    end
    seq
end