some sort benchmarks

result

======== random  2097152 =============
(0.185) 2097152 elements with original quick sort
(0.135) 2097152 elements with intro sort
(0.142) 2097152 elements with std::sort in cpp
(0.267) 2097152 elements with qsort in c
======== seq  2097152 =============
(0.047) 2097152 elements with original quick sort
(0.021) 2097152 elements with intro sort
(0.025) 2097152 elements with std::sort in cpp
(0.076) 2097152 elements with qsort in c
======== rotated_seq  2097152 =============
(0.065) 2097152 elements with original quick sort
(0.123) 2097152 elements with intro sort
(0.044) 2097152 elements with std::sort in cpp
(0.081) 2097152 elements with qsort in c
======== reversed  2097152 =============
(0.047) 2097152 elements with original quick sort
(0.198) 2097152 elements with intro sort
(0.018) 2097152 elements with std::sort in cpp
(0.096) 2097152 elements with qsort in c
======== rotated_reversed  2097152 =============
(0.047) 2097152 elements with original quick sort
(0.197) 2097152 elements with intro sort
(0.118) 2097152 elements with std::sort in cpp
(0.102) 2097152 elements with qsort in c
======== random  4194304 =============
(0.379) 4194304 elements with original quick sort
(0.282) 4194304 elements with intro sort
(0.296) 4194304 elements with std::sort in cpp
(0.552) 4194304 elements with qsort in c
======== seq  4194304 =============
(0.097) 4194304 elements with original quick sort
(0.044) 4194304 elements with intro sort
(0.053) 4194304 elements with std::sort in cpp
(0.160) 4194304 elements with qsort in c
======== rotated_seq  4194304 =============
(0.131) 4194304 elements with original quick sort
(0.311) 4194304 elements with intro sort
(0.263) 4194304 elements with std::sort in cpp
(0.170) 4194304 elements with qsort in c
======== reversed  4194304 =============
(0.095) 4194304 elements with original quick sort
(0.425) 4194304 elements with intro sort
(0.038) 4194304 elements with std::sort in cpp
(0.200) 4194304 elements with qsort in c
======== rotated_reversed  4194304 =============
(0.100) 4194304 elements with original quick sort
(0.425) 4194304 elements with intro sort
(0.318) 4194304 elements with std::sort in cpp
(0.202) 4194304 elements with qsort in c
======== random  8388608 =============
(0.789) 8388608 elements with original quick sort
(0.596) 8388608 elements with intro sort
(0.612) 8388608 elements with std::sort in cpp
(1.148) 8388608 elements with qsort in c
======== seq  8388608 =============
(0.201) 8388608 elements with original quick sort
(0.097) 8388608 elements with intro sort
(0.110) 8388608 elements with std::sort in cpp
(0.341) 8388608 elements with qsort in c
======== rotated_seq  8388608 =============
(0.280) 8388608 elements with original quick sort
(0.285) 8388608 elements with intro sort
(0.133) 8388608 elements with std::sort in cpp
(0.355) 8388608 elements with qsort in c
======== reversed  8388608 =============
(0.204) 8388608 elements with original quick sort
(0.905) 8388608 elements with intro sort
(0.081) 8388608 elements with std::sort in cpp
(0.418) 8388608 elements with qsort in c
======== rotated_reversed  8388608 =============
(0.211) 8388608 elements with original quick sort
(0.880) 8388608 elements with intro sort
(0.755) 8388608 elements with std::sort in cpp
(0.428) 8388608 elements with qsort in c
======== random  16777216 =============
(1.651) 16777216 elements with original quick sort
(1.238) 16777216 elements with intro sort
(1.297) 16777216 elements with std::sort in cpp
(2.484) 16777216 elements with qsort in c
======== seq  16777216 =============
(0.418) 16777216 elements with original quick sort
(0.188) 16777216 elements with intro sort
(0.224) 16777216 elements with std::sort in cpp
(0.706) 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.615) 16777216 elements with original quick sort
(1.723) 16777216 elements with intro sort
(1.128) 16777216 elements with std::sort in cpp
(0.729) 16777216 elements with qsort in c
======== reversed  16777216 =============
(0.413) 16777216 elements with original quick sort
(1.871) 16777216 elements with intro sort
(0.181) 16777216 elements with std::sort in cpp
(0.923) 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.443) 16777216 elements with original quick sort
(1.815) 16777216 elements with intro sort
(1.008) 16777216 elements with std::sort in cpp
(0.895) 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

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: "#{__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