Insertion sort

The best analogy for insertion sort is a deck of cards. And you need to put them in the right order from smallest to greatest. You hold at least one card constant while you move the other cards around it to sort everything into order. The element that you considering could be moved one spot or over multiple spots.

def insertion_sort(array)
  return array if array.size <= 1

  (array.length).times do |i|
    while i > 0
      if array[i-1] > array[i]
        array[i], array[i-1] = array[i-1], array[i]
      else
        break
      end
      i-=1
    end
  end
  array
end

• return array if it's empty or include one element
• iterate through array with (array.length).times, i represents the index of the array
• in the loops when element's index > 0
• we set if/else condition and if previous value larger than current we swap them, else we terminate loops
• if loops does not terminate we decrease index of array and continue

Time Complexity: О(n^2)
Space Complexity: О(n)