module Helpers

def partition!(range, &block)
  return range.begin...range.begin, range if range.one?
  last, pivot = range.end - 1, Kernel.rand(range)
  self[pivot], self[last] = self[last], self[pivot]
  pivot_value = block.call(at last)
  index = range.inject(range.begin) do |store, index|
    next store unless index == last || block.call(at index) < pivot_value
    self[index], self[store] = self[store], self[index]
    store + 1
  end
  return range.begin...index, index...range.end
end