final comparaison between libc.qsort, qsort and dsort in crystal

dsort.cr

################################  Crystall scripts

def  chrono(text)
 s=Time.now
 yield
 e=Time.now
 d=(e.to_f-s.to_f)*1000
 if d>1
   puts "#{text} : #{d} ms"
 else
   puts "#{text} : #{d*1000} micro s"
 end
end 

class  Array
 def *(c0: Int)
   l=self.clone
   return l if c0<=0
   c=c0-1
   while c>0
    if l.size>self.size && c>=(l.size/self.size)
       c=c-(l.size/self.size)
       l = l + l.clone
    else
       l = l  +  self.clone
       c-=1
    end
   end
   l
 end
end

lib C
  fun qsort(base : Void*, nel : Int32, width : Int32, cb : (Void*, Void*) -> Int32)
end



def libc_qsort(a)
 b=a.clone
 compar = ->(x : Void*, y : Void*) do (x as Int32*).value <=> (y as Int32*).value end
 C.qsort(b.buffer as Void*, b.length, 4, compar)
 b
end

##################### insertion sort

def isort(a)
  1.upto(a.length - 1) do |i|
    value = a[i]
    j = i - 1
    while j >= 0 &&  a[j] > value
      a[j+1] = a[j]
      j -= 1
    end
    a[j+1] = value
  end
  a
end

######### doubl pivot sort: trnscript from Java Vladimir Yaroslavskiy implementation

macro swap(a,i,j)
  {{a}}[{{i}}],{{a}}[{{j}}]={{a}}[{{j}}],{{a}}[{{i}}]
end

#def swap(a,i,j) a[i],a[j]=a[j],a[i] ; end

def dsort1(a : Array( Int32 ), left: Int32,  right: Int32,  div: Int32)
    return if right<=left
    len = right - left;
    if len < 27
      isort(a)
      return
    end
    if left>0
      while a[left-1]<a[left]
        left+=1 
        return  if left>=right
      end
    end
    third = len / div;
    m1 = left  + third;
    m2 = right - third;
    if a[m1] < a[m2] 
        swap(a, m1, left)
        swap(a, m2, right)
    else 
        swap(a, m1, right)
        swap(a, m2, left)
    end
    pivot1 = a[left]
    pivot2 = a[right]
    less=left+1
    great=right - 1
    k=less
    while k<=great
      if a[k] < pivot1
          swap(a, k, less)
          less+=1
      elsif a[k] >= pivot2
        great-=1 while k < great && a[great] > pivot2
        swap(a, k, great);
        great-=1
        if a[k] < pivot1
          swap(a, k, less) 
          less-=1
        end
      end 
      k+=1
    end
    less-=1
    great+=1
    swap(a, less  , left);
    swap(a, great , right);

    dsort1(a,left,   less - 1, div)
    dsort1(a,less+1, great-1, div)
    dsort1(a,great + 1, right, div)
end

def dsort(a)
  dsort1(a,0,a.size-1,3)
  a
end


##################################################################
#       T e s t          a n d         m e a s u r e s
##################################################################

[
(1..1000).map {|a| a/4 },
(1..10000).to_a.reverse,
(1..10000).to_a.shuffle,
[2]*100,
(0..20_000).map {|a| a*a} + (0..20_000).map {|a| a*a} ,
(1000..10000).to_a+(1..1000-1).to_a.shuffle,
(1000..100000).to_a+(1..1000-1).to_a.shuffle,
(0..20_000).map {|a| a*a}.shuffle ,
(0..1000_000).to_a.shuffle,
(0..3_000_000).to_a.shuffle,
].each {|a|
  puts "\n===== %s.. len=%d" % [a.first(10).join(", "),a.size]
  ref=a.clone.sort
  chrono("native") { p "error" unless a.clone.sort()==ref }
  chrono("  LibC") { p "error" unless libc_qsort(a.clone)==ref }
  chrono(" dsort") { p "error" unless dsort(a.clone)==ref }
}

===== 0, 0, 0, 1, 1, 1, 1, 2, 2, 2.. len=1000
native : 14.0667 micro s
LibC : 83.9233 micro s
dsort : 190.973 micro s

===== 10000, 9999, 9998, 9997, 9996, 9995, 9994, 9993, 9992, 9991.. len=10000
native : 132.799 micro s
LibC : 355.959 micro s
dsort : 47.2729 ms

===== 2964, 4413, 2705, 4692, 1628, 9866, 4621, 9942, 3042, 5978.. len=10000
native : 517.845 micro s
LibC : 809.908 micro s
dsort : 23.715 ms

===== 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.. len=100
native : 0.953674 micro s
LibC : 1.90735 micro s
dsort : 3.09944 micro s

===== 0, 1, 4, 9, 16, 25, 36, 49, 64, 81.. len=40002
native : 211.877 ms
LibC : 1.25098 ms
dsort : 472.006 ms

===== 1000, 1001, 1002, 1003, 1004, 1005, 1006, 1007, 1008, 1009.. len=10000
native : 223.875 micro s
LibC : 319.958 micro s
dsort : 14.2 ms

===== 1000, 1001, 1002, 1003, 1004, 1005, 1006, 1007, 1008, 1009.. len=100000
native : 1.87206 ms
LibC : 3.01886 ms
dsort : 158.101 ms

===== 191213584, 165868641, 182115025, 175642009, 308915776, 386476281, 11236, 396209025, 185368225, 26574025.. len=20001
native : 1.09911 ms
LibC : 1.71304 ms
dsort : 95.6991 ms

===== 618292, 519061, 256006, 149742, 942648, 94, 576885, 700268, 205964, 744503.. len=1000001
native : 75.8259 ms
LibC : 116.51 ms
Program terminated abnormally with error code: 2