some sort benchmarks

result

# Intel(R) Xeon(R) CPU E5-2620 0 @ 2.00GHz
# Arch Linux x86_64
# g++ (GCC) 6.2.1 20160830
# Crystal 0.19.4 (2016-10-07)

======== random  2097152 =============
(0.333) 2097152 elements with original quick sort
(0.247) 2097152 elements with intro sort
(0.245) 2097152 elements with std::sort in cpp
(0.444) 2097152 elements with qsort in c
======== seq  2097152 =============
(0.057) 2097152 elements with original quick sort
(0.029) 2097152 elements with intro sort
(0.051) 2097152 elements with std::sort in cpp
(0.122) 2097152 elements with qsort in c
======== rotated_seq  2097152 =============
(0.093) 2097152 elements with original quick sort
(0.047) 2097152 elements with intro sort
(0.073) 2097152 elements with std::sort in cpp
(0.126) 2097152 elements with qsort in c
======== reversed  2097152 =============
(0.057) 2097152 elements with original quick sort
(0.055) 2097152 elements with intro sort
(0.040) 2097152 elements with std::sort in cpp
(0.138) 2097152 elements with qsort in c
======== rotated_reversed  2097152 =============
(0.059) 2097152 elements with original quick sort
(0.058) 2097152 elements with intro sort
(0.308) 2097152 elements with std::sort in cpp
(0.140) 2097152 elements with qsort in c
======== random  4194304 =============
(0.597) 4194304 elements with original quick sort
(0.505) 4194304 elements with intro sort
(0.515) 4194304 elements with std::sort in cpp
(0.929) 4194304 elements with qsort in c
======== seq  4194304 =============
(0.121) 4194304 elements with original quick sort
(0.060) 4194304 elements with intro sort
(0.106) 4194304 elements with std::sort in cpp
(0.257) 4194304 elements with qsort in c
======== rotated_seq  4194304 =============
(0.168) 4194304 elements with original quick sort
(0.105) 4194304 elements with intro sort
(0.200) 4194304 elements with std::sort in cpp
(0.267) 4194304 elements with qsort in c
======== reversed  4194304 =============
(0.118) 4194304 elements with original quick sort
(0.116) 4194304 elements with intro sort
(0.082) 4194304 elements with std::sort in cpp
(0.291) 4194304 elements with qsort in c
======== rotated_reversed  4194304 =============
(0.125) 4194304 elements with original quick sort
(0.112) 4194304 elements with intro sort
(0.738) 4194304 elements with std::sort in cpp
(0.298) 4194304 elements with qsort in c
======== random  8388608 =============
(1.255) 8388608 elements with original quick sort
(1.072) 8388608 elements with intro sort
(1.087) 8388608 elements with std::sort in cpp
(1.968) 8388608 elements with qsort in c
======== seq  8388608 =============
(0.250) 8388608 elements with original quick sort
(0.127) 8388608 elements with intro sort
(0.226) 8388608 elements with std::sort in cpp
(0.538) 8388608 elements with qsort in c
======== rotated_seq  8388608 =============
(0.346) 8388608 elements with original quick sort
(0.212) 8388608 elements with intro sort
(0.282) 8388608 elements with std::sort in cpp
(0.570) 8388608 elements with qsort in c
======== reversed  8388608 =============
(0.247) 8388608 elements with original quick sort
(0.242) 8388608 elements with intro sort
(0.175) 8388608 elements with std::sort in cpp
(0.619) 8388608 elements with qsort in c
======== rotated_reversed  8388608 =============
(0.260) 8388608 elements with original quick sort
(0.228) 8388608 elements with intro sort
(1.410) 8388608 elements with std::sort in cpp
(0.630) 8388608 elements with qsort in c
======== random  16777216 =============
(2.631) 16777216 elements with original quick sort
(2.236) 16777216 elements with intro sort
(2.327) 16777216 elements with std::sort in cpp
(4.211) 16777216 elements with qsort in c
======== seq  16777216 =============
(0.590) 16777216 elements with original quick sort
(0.273) 16777216 elements with intro sort
(0.483) 16777216 elements with std::sort in cpp
(1.296) 16777216 elements with qsort in c
======== rotated_seq  16777216 =============
GC Warning: Repeated allocation of very large block (appr. size 67112960):
	May lead to memory leak and poor performance
(0.874) 16777216 elements with original quick sort
(0.514) 16777216 elements with intro sort
(0.556) 16777216 elements with std::sort in cpp
(1.175) 16777216 elements with qsort in c
======== reversed  16777216 =============
(0.597) 16777216 elements with original quick sort
(0.540) 16777216 elements with intro sort
(0.375) 16777216 elements with std::sort in cpp
(1.307) 16777216 elements with qsort in c
======== rotated_reversed  16777216 =============
GC Warning: Repeated allocation of very large block (appr. size 67112960):
	May lead to memory leak and poor performance
(0.600) 16777216 elements with original quick sort
(0.481) 16777216 elements with intro sort
(2.905) 16777216 elements with std::sort in cpp
(1.313) 16777216 elements with qsort in c

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

def report(msg)
  t = Time.now
  s = 0_64
  yield || 0
  puts "(#{"%.3f" % {(Time.now - t).to_f}}) #{msg}"
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)
    b, c, d = a.dup, a.dup, a.dup
    report("#{size} elements with original quick sort") do
      a.sort!
    end
    report("#{size} elements with intro sort") do
      b.intro_sort!
    end
    report("#{size} elements with std::sort in cpp") do
      StdSort.std_sort(c, size)
    end
    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