require 'minitest'
require 'minitest/autorun'
require 'benchmark/ips'

def quicksort(ary)
  ary = ary.dup
  return [] if ary.empty?

  pivot = ary.delete_at(rand(ary.size))

  left, right = [], []

  ary.each do |val|
    target = val <= pivot ? left : right
    target << val
  end

  quicksort(left)
    .concat([pivot])
    .concat(quicksort(right))
end

SAMPLE_SET = (1..100).to_a
EXAMPLE = SAMPLE_SET.shuffle
Benchmark.ips do |x|
  x.report("quicksort") do
    quicksort(EXAMPLE)
  end
  x.report("ruby sort") do
    EXAMPLE.sort
  end
  x.compare!
end

class SortingTest < Minitest::Test
  def test_sorting_works
    100.times do
      assert_equal EXAMPLE.sort, quicksort(EXAMPLE)
    end
  end
end