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

def mark_sort(array)
  array_max = array.max
  array_min = array.min
  markings = [0] * (array_max - array_min + 1)
  array.each do |a|
    markings[a - array_min] += 1
  end

  res = []
  markings.length.times do |i|
    markings[i].times do
      res << i + array_min;
    end
  end

  res
end

SAMPLE_SET = (1..100).to_a
EXAMPLE = SAMPLE_SET.shuffle
Benchmark.ips do |x|
  x.report("mark sort") do
    mark_sort(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, mark_sort(EXAMPLE)
    end
  end
end