insertion_sort.rb

class InsertionSort
  def initialize(list)
    @list = list
    @sorted = []
  end

  def sort
    insert(@list.shift) while @list.length > 0
    @sorted
  end

  private

  def insert(x)
    head = @sorted.select{ |i| i <= x }
    tail = @sorted.select{ |i| i > x }
    @sorted = head + [x] + tail
  end

end

# puts InsertionSort.new([]).sort.inspect
# puts InsertionSort.new([4]).sort.inspect
# puts InsertionSort.new([1, 4]).sort.inspect
# puts InsertionSort.new([4, 1]).sort.inspect
# puts InsertionSort.new([4, 1, 3, 5, 6]).sort.inspect
# puts InsertionSort.new([4, 1, 3, 5, 6, 2]).sort.inspect
# puts InsertionSort.new([4, 1, 3, 5, 6, 2, 2]).sort.inspect