require 'benchmark'

def quicksort(entry, method)
  return entry if entry.size <= 1
  pivot = identify_pivot(entry, method)
  left, right = entry.partition {|e| e < pivot}
  quicksort(left, method) + [pivot] + quicksort(right, method)
end

def identify_pivot(entry, method)
  return entry.pop if method == 'first'
  return entry.delete_at(entry.index(medium(entry[0..2]))) if method == 'three'
  return entry.delete_at(entry.index(medium(entry[0..4]))) if method == 'five'
end

def medium(entry)
  return entry.sort[(entry.size/2).floor]
end

entry = (1..1000000).map {rand}

Benchmark.bmbm do |r|
  r.report("first") {quicksort(entry.dup, 'first')}
  r.report("three") {quicksort(entry.dup, 'three')}
  r.report("five")  {quicksort(entry.dup, 'five')}
  r.report("sort")  {entry.dup.sort}
  r.report("sort!") {entry.dup.sort!}
end