result

# AMD Athlon(tm) II X2 270 Processor
# Arch Linux x86_64
# gcc (GCC) 6.2.1 20160830
# Crystal 0.19.4 (2016-10-07)
======== random2  2097152 =============
        with intro sort   6.82  (± 7.91%)       fastest
with another intro sort   6.22  (± 7.18%)  1.10× slower
  with std::sort in cpp   6.74  (± 7.34%)  1.01× slower
        with qsort in c   3.59  (± 5.62%)  1.90× slower
======== seq  2097152 =============
        with intro sort  27.56  (± 8.05%)       fastest
with another intro sort  18.64  (±11.13%)  1.48× slower
  with std::sort in cpp  18.85  (± 9.71%)  1.46× slower
        with qsort in c  10.83  (± 7.18%)  2.54× slower
======== rotated_seq  2097152 =============
        with intro sort  18.64  (±10.24%)       fastest
with another intro sort   4.99  (± 4.12%)  3.73× slower
  with std::sort in cpp   6.01  (± 2.93%)  3.10× slower
        with qsort in c  10.58  (± 8.31%)  1.76× slower
======== reversed  2097152 =============
        with intro sort  25.68  (±12.16%)       fastest
with another intro sort  22.22  (± 8.45%)  1.16× slower
  with std::sort in cpp   22.2  (± 7.69%)  1.16× slower
        with qsort in c   8.53  (± 5.00%)  3.01× slower
======== rotated_reversed  2097152 =============
        with intro sort   17.8  (± 8.78%)       fastest
with another intro sort   3.39  (± 8.02%)  5.26× slower
  with std::sort in cpp   3.87  (± 7.21%)  4.60× slower
        with qsort in c   8.34  (± 6.88%)  2.13× slower
======== random2  4194304 =============
        with intro sort   3.35  (± 6.52%)       fastest
with another intro sort   2.96  (± 7.37%)  1.13× slower
  with std::sort in cpp   3.28  (± 6.09%)  1.02× slower
        with qsort in c   1.75  (± 7.23%)  1.91× slower
======== seq  4194304 =============
        with intro sort  13.13  (± 7.65%)       fastest
with another intro sort   8.78  (± 6.49%)  1.49× slower
  with std::sort in cpp   8.82  (± 8.90%)  1.49× slower
        with qsort in c   4.88  (± 6.82%)  2.69× slower
======== rotated_seq  4194304 =============
        with intro sort   7.69  (± 8.09%)       fastest
with another intro sort   2.57  (± 7.92%)  3.00× slower
  with std::sort in cpp   2.89  (± 5.92%)  2.66× slower
        with qsort in c   4.86  (± 9.34%)  1.58× slower
======== reversed  4194304 =============
        with intro sort  12.83  (± 8.07%)  1.02× slower
with another intro sort  12.35  (± 6.92%)  1.06× slower
  with std::sort in cpp  13.11  (± 5.98%)       fastest
        with qsort in c   4.19  (± 4.69%)  3.13× slower
======== rotated_reversed  4194304 =============
        with intro sort   7.92  (± 8.36%)       fastest
with another intro sort   2.68  (± 5.63%)  2.96× slower
  with std::sort in cpp   3.03  (± 5.56%)  2.62× slower
        with qsort in c   3.91  (± 7.03%)  2.03× slower
======== random2  8388608 =============
        with intro sort   1.57  (± 5.31%)  1.02× slower
with another intro sort   1.36  (± 5.06%)  1.18× slower
  with std::sort in cpp   1.61  (± 6.65%)       fastest
        with qsort in c   0.87  (± 5.17%)  1.84× slower
======== seq  8388608 =============
        with intro sort   6.41  (± 6.98%)       fastest
with another intro sort   4.11  (± 7.46%)  1.56× slower
  with std::sort in cpp   4.33  (± 7.08%)  1.48× slower
        with qsort in c    2.5  (± 7.01%)  2.56× slower
======== rotated_seq  8388608 =============
        with intro sort   4.04  (± 3.89%)       fastest
with another intro sort   2.39  (± 4.76%)  1.69× slower
  with std::sort in cpp   2.71  (± 4.62%)  1.49× slower
        with qsort in c   2.29  (± 5.36%)  1.76× slower
======== reversed  8388608 =============
        with intro sort   6.47  (± 6.25%)       fastest
with another intro sort    5.6  (± 6.66%)  1.15× slower
  with std::sort in cpp   6.21  (± 6.99%)  1.04× slower
        with qsort in c   1.82  (± 7.07%)  3.56× slower
======== rotated_reversed  8388608 =============
        with intro sort   3.95  (± 7.70%)       fastest
with another intro sort   1.25  (± 6.38%)  3.15× slower
  with std::sort in cpp   1.48  (± 4.72%)  2.67× slower
        with qsort in c    1.9  (± 4.11%)  2.08× slower
======== random2  16777216 =============
        with intro sort   0.75  (± 2.68%)  1.01× slower
with another intro sort   0.71  (± 4.48%)  1.07× slower
  with std::sort in cpp   0.76  (± 3.27%)       fastest
        with qsort in c   0.42  (± 4.31%)  1.80× slower
======== seq  16777216 =============
        with intro sort   3.02  (± 4.85%)       fastest
with another intro sort   2.01  (± 4.13%)  1.50× slower
  with std::sort in cpp   2.03  (± 6.83%)  1.49× slower
        with qsort in c   1.15  (± 2.41%)  2.62× slower
======== rotated_seq  16777216 =============
        with intro sort   1.78  (± 4.24%)       fastest
with another intro sort   0.93  (± 3.38%)  1.92× slower
  with std::sort in cpp   1.04  (± 3.41%)  1.71× slower
        with qsort in c   1.08  (± 3.78%)  1.64× slower
======== reversed  16777216 =============
        with intro sort   2.96  (± 5.49%)  1.00× slower
with another intro sort   2.71  (± 6.26%)  1.09× slower
  with std::sort in cpp   2.96  (± 6.74%)       fastest
        with qsort in c   0.88  (± 3.88%)  3.35× slower
======== rotated_reversed  16777216 =============
        with intro sort    1.7  (± 4.34%)       fastest
with another intro sort    0.4  (± 1.55%)  4.23× slower
  with std::sort in cpp   0.44  (± 2.45%)  3.86× slower
        with qsort in c   0.92  (± 5.72%)  1.84× 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"

@[AlwaysInline]
def log(a : Int)
  k = 0
  while a > 0
    k, a = k + 1, a >> 1
  end
  k - 1
end

struct Pointer
  @[AlwaysInline]  
  def succ
    self + 1
  end

  @[AlwaysInline]
  def pred
    self - 1
  end
end

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, log(n) * 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

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

  protected def self.heap_sort!(a, n)
    (n / 2).downto 0 do |p|
      heapify!(a, p, n)
    end

    ((a + 1)...(a + n)).reverse_each do |p|
      a.value, p.value = p.value, a.value
      heapify!(a, 0, p - a)
    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.even? && 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 = c.value, a.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)
    ((a + 1)...(a + n)).each do |l|
      v = l.value
      (a...l).reverse_each do |p|
        break unless v < p.value
        l.value = p.value
        l -= 1
      end
      l.value = v
    end
  end

  def intro_sort2!
    Array.intro_sort2!(@buffer, @buffer + @size)
    self
  end

  protected def self.intro_sort2!(first, last)
    n = last - first
    return if n < 2
    quick_sort2!(first, last, log(n) * 2)
    insertion_sort2!(first, last)
  end

  protected def self.quick_sort2!(first, last, d)
    while (last - first) > 16
      if d == 0
        heap_sort!(first, last - first)
        return
      end
      d -= 1
      cut = partition_pivot!(first, last)
      quick_sort2!(cut, last, d)
      last = cut
    end
  end

  protected def self.partition_pivot!(first, last)
    mid = first + (last - first)/2
    move_median_to_first!(first, first + 1, mid, last - 1)
    partition2!(first + 1, last, first)
  end

  protected def self.move_median_to_first!(result, a, b, c)
    if a.value <= b.value
      if b.value <= c.value
        result.value, b.value = b.value, result.value
      elsif a.value <= c.value
        result.value, c.value = c.value, result.value
      else
        result.value, a.value = a.value, result.value
      end
    elsif a.value <= c.value
      result.value, a.value = a.value, result.value
    elsif b.value <= c.value
      result.value, c.value = c.value, result.value
    else
      result.value, b.value = b.value, result.value
    end
  end

  protected def self.partition2!(first, last, pivot)
    v = pivot.value
    loop do
      while first.value < v
        first += 1
      end
      last -= 1
      while v < last.value
        last -= 1
      end
      return first unless first < last
      first.value, last.value = last.value, first.value
      last += 1
    end
  end

  protected def self.insertion_sort2!(first, last)
    ((first + 1)...last).each do |l|
      v = l.value
      (first...l).reverse_each do |p|
        break unless v < p.value
        l.value = p.value
        l -= 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 = [] of Int32
    a.fill(0...size) { |i| random.next_int }
  when :random2
    (0...size).to_a.shuffle
  when :seq
    (0...size).to_a
  when :rotated_seq
    (0...size).to_a.rotate(rand(size))
  when :reversed
    (0...size).to_a.reverse
  when :rotated_reversed
    (0...size).to_a.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
  [:random2, :seq, :rotated_seq, :reversed, :rotated_reversed].each do |style|
    puts "======== #{style}  #{size} ============="
    a = generate_array(size, style)
    sorted_a = a.sort
    Benchmark.ips(10) do |x|
      x.before_all do
        Test.array.replace(a)
      end
      x.report("with intro sort") do
        Test.array.intro_sort!
        raise Exception.new "sort failed" unless Test.array == sorted_a
      end
      x.report("with another intro sort") do
        Test.array.intro_sort2!
        raise Exception.new "sort failed" unless Test.array == sorted_a
      end
      x.report("with std::sort in cpp") do
        StdSort.std_sort(Test.array, size)
        raise Exception.new "sort failed" unless Test.array == sorted_a
      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
        })
        raise Exception.new "sort failed" unless Test.array == sorted_a
      end

    end
  end
  size *= 2
end

Not tested cases where values are heavily repeated:

• few distinct values (for example, 5 differrent values in array)
• one value consumed 90% of items,
• etc.