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 }
}