result

# Intel(R) Core(TM) i7-4770 CPU @ 3.40GHz
# Arch Linux x86_64
# g++ (GCC) 6.2.1 20160830
# Crystal 0.19.4 (2016-10-07)
======== random  2097152 =============
with original quick sort   6.73  (± 2.34%)  1.16× slower
         with intro sort   7.84  (± 1.49%)       fastest
   with std::sort in cpp   7.83  (± 1.74%)  1.00× slower
         with qsort in c   4.98  (± 1.75%)  1.57× slower
======== seq  2097152 =============
with original quick sort  42.68  (± 3.38%)  1.80× slower
         with intro sort  76.61  (± 3.35%)       fastest
   with std::sort in cpp  40.78  (± 2.71%)  1.88× slower
         with qsort in c  18.35  (± 4.09%)  4.17× slower
======== rotated_seq  2097152 =============
with original quick sort  35.82  (± 4.83%)  1.81× slower
         with intro sort  64.71  (± 4.57%)       fastest
   with std::sort in cpp   38.7  (± 3.97%)  1.67× slower
         with qsort in c  17.23  (± 3.90%)  3.76× slower
======== reversed  2097152 =============
with original quick sort  42.34  (± 2.87%)  1.38× slower
         with intro sort  58.24  (± 4.31%)       fastest
   with std::sort in cpp  42.29  (± 3.39%)  1.38× slower
         with qsort in c  15.87  (± 5.01%)  3.67× slower
======== rotated_reversed  2097152 =============
with original quick sort  42.24  (± 2.27%)  1.43× slower
         with intro sort  60.21  (± 3.20%)       fastest
   with std::sort in cpp   6.68  (± 2.17%)  9.02× slower
         with qsort in c  15.57  (± 2.94%)  3.87× slower
======== random  4194304 =============
with original quick sort   3.21  (± 1.55%)  1.16× slower
         with intro sort   3.72  (± 1.29%)  1.00× slower
   with std::sort in cpp   3.74  (± 1.38%)       fastest
         with qsort in c   2.32  (± 1.41%)  1.61× slower
======== seq  4194304 =============
with original quick sort  19.97  (± 3.26%)  1.78× slower
         with intro sort  35.54  (± 3.47%)       fastest
   with std::sort in cpp  19.29  (± 3.37%)  1.84× slower
         with qsort in c    8.9  (± 3.08%)  3.99× slower
======== rotated_seq  4194304 =============
with original quick sort  13.37  (± 3.86%)  1.60× slower
         with intro sort  21.32  (± 4.48%)       fastest
   with std::sort in cpp   6.07  (± 2.50%)  3.51× slower
         with qsort in c   8.37  (± 3.66%)  2.55× slower
======== reversed  4194304 =============
with original quick sort   20.3  (± 4.32%)  1.06× slower
         with intro sort  19.15  (± 4.10%)  1.12× slower
   with std::sort in cpp  21.48  (± 3.53%)       fastest
         with qsort in c   7.44  (± 3.97%)  2.89× slower
======== rotated_reversed  4194304 =============
with original quick sort  19.54  (± 3.23%)       fastest
         with intro sort   18.5  (± 3.89%)  1.06× slower
   with std::sort in cpp   3.17  (± 2.74%)  6.17× slower
         with qsort in c   7.32  (± 3.53%)  2.67× slower
======== random  8388608 =============
with original quick sort   1.55  (± 1.27%)  1.15× slower
         with intro sort   1.79  (± 1.21%)       fastest
   with std::sort in cpp   1.78  (± 1.54%)  1.01× slower
         with qsort in c    1.1  (± 1.70%)  1.63× slower
======== seq  8388608 =============
with original quick sort    9.6  (± 3.46%)  1.76× slower
         with intro sort  16.86  (± 3.65%)       fastest
   with std::sort in cpp   8.85  (± 6.02%)  1.91× slower
         with qsort in c   4.05  (± 3.62%)  4.16× slower
======== rotated_seq  8388608 =============
GC Warning: Repeated allocation of very large block (appr. size 33558528):
        May lead to memory leak and poor performancetest
with original quick sort   5.21  (± 2.80%)  1.84× slower
         with intro sort   8.67  (± 2.93%)  1.11× slower
   with std::sort in cpp   9.61  (± 2.97%)       fastest
         with qsort in c    3.8  (± 2.52%)  2.53× slower
======== reversed  8388608 =============
with original quick sort   9.58  (± 3.99%)  1.22× slower
         with intro sort   9.17  (± 3.30%)  1.28× slower
   with std::sort in cpp  11.71  (± 4.15%)       fastest
         with qsort in c   3.56  (± 3.05%)  3.29× slower
======== rotated_reversed  8388608 =============
with original quick sort   9.56  (± 4.36%)       fastest
         with intro sort   9.45  (± 3.10%)  1.01× slower
   with std::sort in cpp   1.75  (± 3.31%)  5.47× slower
         with qsort in c   3.41  (± 9.26%)  2.80× slower
======== random  16777216 =============
GC Warning: Repeated allocation of very large block (appr. size 67112960):
        May lead to memory leak and poor performancetest
with original quick sort   0.75  (± 0.43%)  1.14× slower
         with intro sort   0.84  (± 3.09%)  1.01× slower
   with std::sort in cpp   0.85  (± 0.69%)       fastest
         with qsort in c   0.53  (± 0.58%)  1.61× slower
======== seq  16777216 =============
with original quick sort   4.72  (± 2.89%)  1.71× slower
         with intro sort   8.05  (± 3.77%)       fastest
   with std::sort in cpp   4.31  (± 1.99%)  1.87× slower
         with qsort in c   1.98  (± 3.08%)  4.06× slower
======== rotated_seq  16777216 =============
with original quick sort   2.89  (± 1.34%)  1.69× slower
         with intro sort   4.89  (± 2.83%)       fastest
   with std::sort in cpp   2.79  (± 2.29%)  1.75× slower
         with qsort in c   1.88  (± 3.61%)  2.60× slower
======== reversed  16777216 =============
GC Warning: Repeated allocation of very large block (appr. size 67112960):
	May lead to memory leak and poor performance
with original quick sort   4.72  (± 2.16%)  1.19× slower
         with intro sort   4.29  (± 2.08%)  1.30× slower
   with std::sort in cpp   5.59  (± 2.25%)       fastest
         with qsort in c   1.68  (± 0.97%)  3.32× slower
======== rotated_reversed  16777216 =============
with original quick sort   4.57  (± 2.20%)  1.01× slower
         with intro sort    4.6  (± 2.33%)       fastest
   with std::sort in cpp   0.72  (± 1.25%)  6.40× slower
         with qsort in c   1.64  (± 1.50%)  2.81× slower

sort.cpp

// g++ -c -O3 -o sort.o sort.cpp
#include <cstdlib>
#include <algorithm>
extern "C" void std_sort(int *array, int size) {
  std::sort(array, array + size);
}

sort_benchmarks.cr

# crystal build --release sort_benchmarks.cr
require "benchmark"

class Array
  def intro_sort!
    Array.intro_sort!(@buffer, @size)
    self
  end

  protected def self.intro_sort!(a, n)
    return if n < 2
    quick_sort!(a, n, Math.log2(n).to_i * 2)
    insertion_sort!(a, n)
  end

  protected def self.quick_sort!(a, n, d)
    while n > 16
      if d == 0
        heap_sort!(a, n)
        return
      end
      d -= 1
      center_median!(a, n)
      c = partition!(a, n)
      quick_sort!(c, n - (c - a), d)
      n = c - a
    end
  end

  protected def self.heap_sort!(a, n)
    (n / 2).downto 0 do |p|
      heapify!(a, p, n)
    end
    while n > 1
      n -= 1
      a.value, a[n] = a[n], a.value
      heapify!(a, 0, n)
    end
  end

  protected def self.heapify!(a, p, n)
    v, c = a[p], p
    while c < (n - 1) / 2
      c = 2 * (c + 1)
      c -= 1 if a[c] < a[c - 1]
      break unless v <= a[c]
      a[p] = a[c]
      p = c
    end
    if n & 1 == 0 && c == n / 2 - 1
      c = 2 * c + 1
      if v < a[c]
        a[p] = a[c]
        p = c
      end
    end
    a[p] = v
  end

  protected def self.center_median!(a, n)
    b, c = a + n / 2, a + n - 1
    if a.value <= b.value
      if b.value <= c.value
        return
      elsif a.value <= c.value
        b.value, c.value = c.value, b.value
      else
        a.value, b.value, c.value = c.value, a.value, b.value
      end
    elsif a.value <= c.value
      a.value, b.value = b.value, a.value
    elsif b.value <= c.value
      a.value, b.value, c.value = b.value, c.value, a.value
    else
      a.value, c.value = a.value, c.value
    end
  end

  protected def self.partition!(a, n)
    v, l, r = a[n / 2], a + 1, a + n - 1
    loop do
      while l.value < v
        l += 1
      end
      r -= 1
      while v < r.value
        r -= 1
      end
      return l unless l < r
      l.value, r.value = r.value, l.value
      l += 1
    end
  end

  protected def self.insertion_sort!(a, n)
    (1...n).each do |i|
      l = a + i
      v = l.value
      p = l - 1
      while l > a && v < p.value
        l.value = p.value
        l, p = p, p - 1
      end
      l.value = v
    end
  end
end

@[Link(ldflags: "#{__DIR__}/sort.o")]
lib StdSort
  fun std_sort(array : Int32*, size : Int32) : Void
  fun qsort(array : Void*, size : LibC::SizeT, elm_size : LibC::SizeT, cmp : (Void*, Void*) -> Int32)
end

def generate_array(size, style)
  case style
  when :random
    random = Random.new
    a = Array(Int32).new(size)
    size.times do
      a << random.next_int
    end
    a
  when :seq
    Array(Int32).new(size) { |i| i }
  when :rotated_seq
    Array(Int32).new(size) { |i| i }.rotate(rand(size))
  when :reversed
    Array(Int32).new(size) { |i| i }.reverse
  when :rotated_reversed
    Array(Int32).new(size) { |i| i }.reverse.rotate(rand(size))
  else
    raise "unknown style #{style}"
  end
end

module Benchmark
  module IPS
    class Job
      def before_all(&bef)
        @bef = bef
      end

      private def run_warmup
        @items.each do |item|
          GC.collect

          before = Time.now
          target = Time.now + @warmup_time
          count = 0

          while Time.now < target
            @bef.as(->).call unless @bef.nil?
            item.call
            count += 1
          end

          after = Time.now

          item.set_cycles(after - before, count)
        end
      end

      private def run_calculation
        @items.each do |item|
          GC.collect

          measurements = [] of Time::Span
          target = Time.now + @calculation_time

          loop do
            @bef.as(->).call unless @bef.nil?
            before = Time.now
            item.call_for_100ms
            after = Time.now

            measurements << after - before

            break if Time.now >= target
          end

          final_time = Time.now

          ips = measurements.map { |m| item.cycles.to_f / m.total_seconds }
          item.calculate_stats(ips)

          if @interactive
            run_comparison
            report
            print "\e[#{ran_items.size}A"
          end
        end
      end
    end
  end
end

module Test
  @@array : Array(Int32)
  @@array = [] of Int32

  def self.array=(a)
    @@array = a
  end

  def self.array
    @@array
  end
end

size = 2097152
while size <= 16_777_216
  [:random, :seq, :rotated_seq, :reversed, :rotated_reversed].each do |style|
    puts "======== #{style}  #{size} ============="
    a = generate_array(size, style)
    Benchmark.ips(10) do |x|
      x.before_all do
        Test.array = a.dup
      end
      x.report("with original quick sort") do
        Test.array.sort!
      end
      x.report("with intro sort") do
        Test.array.intro_sort!
      end
      x.report("with std::sort in cpp") do
        StdSort.std_sort(Test.array, size)
      end
      x.report("with qsort in c") do
        StdSort.qsort(Test.array, size, sizeof(Int32), ->(x : Void*, y : Void*) {
          x.as(Int32*).value - y.as(Int32*).value
        })
      end
    end
  end
  size *= 2
end