sorted_list_using_divide_and_conquer.rb

# Gets the index for where +obj+ _should_ be, even if it's not in the
# list.
def index_for!(obj)
  divide_and_conquer(
    @array,
    :divisible? => lambda do |list|
      # divide if the list could contain obj
      list.length > 1 && @sorter.call(obj, list.first) > 0 && @sorter.call(obj, list.last) <= 0
    end,
    :divide     => lambda do |list|
      half_index = (list.length / 2)
      [ list[0...half_index], list[(half_index)..-1] ]
    end,
    :conquer    => lambda do |list|
      if list.empty?
        0
      elsif @sorter.call(obj, list.last) > 0
        list.size
      else
        0
      end
    end,
    :recombine  => lambda { |pair| pair.first + pair.last }
  )
end