class Algorithmable::Sort::Insertion

Public Class Methods

sort(collection) click to toggle source

Time О(N^2), stable and slow Space Complexity: О(N)

# File lib/algorithmable/sort/insertion.rb, line 9
def self.sort(collection)
  return collection if 2 > collection.length
  1.upto(collection.length - 1).each do |i|
    curr_char = collection[i]
    j = i - 1
    while 0 <= j && collection[j] > curr_char
      collection[j + 1] = collection[j]
      j -= 1
    end
    collection[j + 1] = curr_char
  end
  collection
end