def insertion_sort(arr)
  final = []
  final << arr.shift
  count_changes = [0]
  for i in arr
    final_index = 0
    while final_index < final.length
      if i <= final[final_index]
        final.insert(final_index,i)
        count_changes.push(count_changes.last + 1)
        break
      elsif final_index == final.length-1
        final.insert(final_index+1,i)
        break
      end
      final_index+=1
    end
  end
  arr.length > 1 ? count_changes.sum : count_changes[0]
end