Re: [PATCH] lib: add statsort(), a distribution/bucket sort

[Peter Taraba]

here are again benchamrks for large arrays:

== n = 100000000  distribution = uniform      ==
  statsort_longs   best of 1:   9.0722 s  (  90.72 ns/elem)
  sort (kernel)    best of 1: 171.2293 s  (1712.29 ns/elem)
  qsort (libc)     best of 1:  18.4959 s  ( 184.96 ns/elem)

== n = 100000000  distribution = gaussian     ==
  statsort_longs   best of 1:   8.6535 s  (  86.54 ns/elem)
  sort (kernel)    best of 1: 170.0339 s  (1700.34 ns/elem)
  qsort (libc)     best of 1:  17.1339 s  ( 171.34 ns/elem)

Faster than qsort (~twice faster) and way faster than qsort(~19 times faster) for both uniform and gaussian distribution.

I only tested with other c file, which I have not included in this patch. Would you like me to add tests? I can easily do so.

As far as usage, just open your mind... I can't tell all my secrets, because I don't want Microsoft to steal them and pretend it was their idea :)