some sort benchmarks

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)
256 elements with original quick sort 702.73k (± 3.72%)  1.50× slower
         256 elements with intro sort   1.05M (± 4.05%)       fastest
   256 elements with std::sort in cpp 845.94k (± 4.23%)  1.25× slower
         256 elements with qsort in c 307.25k (± 5.24%)  3.43× slower
512 elements with original quick sort 320.05k (± 4.60%)  1.51× slower
         512 elements with intro sort 483.13k (± 2.96%)       fastest
   512 elements with std::sort in cpp 368.24k (± 5.18%)  1.31× slower
         512 elements with qsort in c 144.82k (± 2.49%)  3.34× slower
1024 elements with original quick sort 151.42k (± 2.52%)  1.46× slower
         1024 elements with intro sort 221.27k (± 5.39%)       fastest
   1024 elements with std::sort in cpp  168.9k (± 3.60%)  1.31× slower
         1024 elements with qsort in c  66.44k (± 3.24%)  3.33× slower
2048 elements with original quick sort  71.26k (± 1.54%)  1.47× slower
         2048 elements with intro sort 104.46k (± 4.11%)       fastest
   2048 elements with std::sort in cpp  77.55k (± 1.82%)  1.35× slower
         2048 elements with qsort in c  31.59k (± 3.29%)  3.31× slower
4096 elements with original quick sort  33.35k (± 2.99%)  1.49× slower
         4096 elements with intro sort   49.7k (± 2.21%)       fastest
   4096 elements with std::sort in cpp   35.0k (± 3.80%)  1.42× slower
         4096 elements with qsort in c  14.93k (± 3.42%)  3.33× slower
8192 elements with original quick sort  15.79k (± 2.93%)  1.48× slower
         8192 elements with intro sort  23.38k (± 3.43%)       fastest
   8192 elements with std::sort in cpp  16.25k (± 4.94%)  1.44× slower
         8192 elements with qsort in c   6.94k (± 4.09%)  3.37× slower
16384 elements with original quick sort   7.59k (± 1.69%)  1.45× slower
         16384 elements with intro sort  10.99k (± 4.39%)       fastest
   16384 elements with std::sort in cpp    7.7k (± 1.92%)  1.43× slower
         16384 elements with qsort in c   3.32k (± 4.44%)  3.30× slower
32768 elements with original quick sort   3.61k (± 2.24%)  1.48× slower
         32768 elements with intro sort   5.34k (± 2.02%)       fastest
   32768 elements with std::sort in cpp    3.6k (± 3.06%)  1.48× slower
         32768 elements with qsort in c    1.6k (± 1.50%)  3.33× slower
65536 elements with original quick sort   1.71k (± 3.12%)  1.50× slower
         65536 elements with intro sort   2.55k (± 1.50%)       fastest
   65536 elements with std::sort in cpp   1.68k (± 5.23%)  1.52× slower
         65536 elements with qsort in c 760.77  (± 1.61%)  3.36× slower
131072 elements with original quick sort 830.51  (± 1.42%)  1.45× slower
         131072 elements with intro sort    1.2k (± 4.36%)       fastest
   131072 elements with std::sort in cpp 805.25  (± 2.16%)  1.49× slower
         131072 elements with qsort in c 362.45  (± 1.70%)  3.32× slower
262144 elements with original quick sort 397.28  (± 1.93%)  1.45× slower
         262144 elements with intro sort 577.56  (± 3.15%)       fastest
   262144 elements with std::sort in cpp 381.54  (± 2.12%)  1.51× slower
         262144 elements with qsort in c 171.28  (± 2.74%)  3.37× slower
524288 elements with original quick sort 187.54  (± 4.03%)  1.48× slower
         524288 elements with intro sort  277.4  (± 1.82%)       fastest
   524288 elements with std::sort in cpp 177.76  (± 3.75%)  1.56× slower
         524288 elements with qsort in c  81.72  (± 2.55%)  3.39× slower
1048576 elements with original quick sort  90.75  (± 3.21%)  1.39× slower
         1048576 elements with intro sort 125.85  (±10.65%)       fastest
   1048576 elements with std::sort in cpp  85.15  (± 3.06%)  1.48× slower
         1048576 elements with qsort in c  39.37  (± 2.20%)  3.20× slower
2097152 elements with original quick sort   43.6  (± 1.22%)  1.42× slower
         2097152 elements with intro sort  61.93  (± 4.73%)       fastest
   2097152 elements with std::sort in cpp  40.46  (± 2.13%)  1.53× slower
         2097152 elements with qsort in c  18.69  (± 3.23%)  3.31× slower
4194304 elements with original quick sort  20.66  (± 3.98%)  1.45× slower
         4194304 elements with intro sort  29.98  (± 3.41%)       fastest
   4194304 elements with std::sort in cpp  18.75  (± 6.48%)  1.60× slower
         4194304 elements with qsort in c   8.93  (± 2.31%)  3.36× slower
8388608 elements with original quick sort    9.5  (± 5.99%)  1.49× slower
         8388608 elements with intro sort   14.2  (± 2.72%)       fastest
   8388608 elements with std::sort in cpp   8.98  (± 4.58%)  1.58× slower
         8388608 elements with qsort in c   4.17  (± 3.79%)  3.41× slower
16777216 elements with original quick sort   4.86  (± 2.00%)  1.43× slower
         16777216 elements with intro sort   6.96  (± 2.89%)       fastest
   16777216 elements with std::sort in cpp   4.36  (± 2.67%)  1.59× slower
         16777216 elements with qsort in c   1.97  (± 3.94%)  3.53× 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
      shift_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.shift_median!(a, n)
    b, c = a + n / 2, a + n - 1
    if a.value < b.value
      if b.value < c.value
        a.value, b.value = b.value, a.value
      elsif a.value < c.value
        a.value, c.value = c.value, a.value
      end
    elsif a.value < c.value
      return
    elsif b.value < c.value
      a.value, c.value = c.value, a.value
    else
      a.value, b.value = b.value, a.value
    end
  end

  protected def self.partition!(a, n)
    v, l, r = a.value, a + 1, a + n
    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: "/path/to/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)
  random = Random.new
  a = Array(Int32).new(size)
  size.times do
    a << random.next_int
  end
  a
end

size = 256
while size <= 16_777_216
  Benchmark.ips do |x|
    a = generate_array(size)
    b, c, d = a.dup, a.dup, a.dup
    x.report("#{size} elements with original quick sort") do
      a.sort!
    end
    x.report("#{size} elements with intro sort") do
      b.intro_sort!
    end
    x.report("#{size} elements with std::sort in cpp") do
      StdSort.std_sort(c, size)
    end
    x.report("#{size} elements with qsort in c") do
      StdSort.qsort(d, size, sizeof(Int32), -> (x : Void*, y : Void*){
        x.as(Int32*).value - y.as(Int32*).value
      })
    end
  end
  size *= 2
end