# Runtime: 1132 ms, faster than 6.25% of Ruby online submissions for Sort Array By Parity.
# Memory Usage: 9.9 MB, less than 100.00% of Ruby online submissions for Sort Array By Parity.
def sort_array_by_parity(a)
  (0...a.size).each do |i|
    next if a[i] % 2 != 0
    key = a[i]
    while i > 0 && a[i-1] % 2 != 0 do
      a[i] = a[i-1]
      i -= 1
    end
    a[i] = key
  end
  a
end


# Runtime: 84 ms, faster than 6.25% of Ruby online submissions for Sort Array By Parity.
# Memory Usage: 10 MB, less than 100.00% of Ruby online submissions for Sort Array By Parity.
def sort_array_by_parity(a)
  return a if a.size < 2
  middle = a.size / 2
  left = sort_array_by_parity(a[0...middle])
  right = sort_array_by_parity(a[middle..-1])
  merge(left, right)
end

def merge(left, right)
  res = []
  res.push(left[0].even? ? left.shift : right.shift) while !left.empty? && !right.empty?
  res.concat(left).concat(right)
end

# Runtime: 44 ms, faster than 92.19% of Ruby online submissions for Sort Array By Parity.
# Memory Usage: 10.4 MB, less than 75.00% of Ruby online submissions for Sort Array By Parity.

def sort_array_by_parity(a)
  odds, evens = [], []
  a.each {|num| num.odd? ? odds << num : evens << num }
  evens.concat(odds)
end