# primitive-sort

Sorting of contiguous data structures. Implementation uses mergesort
and switches to insertion sort once the arrays are small. Some of the
benchmark results on a Intel Xeon CPU E3-1505M v5 2.80GHz (GHC 8.10.4):

    contiguous/Int8/unsorted/mini      time  91.59 ns  
    contiguous/Int8/unsorted/tiny      time  1.236 μs  
    contiguous/Int8/unsorted/small     time  40.68 μs  
    contiguous/Int8/unsorted/medium    time  614.1 μs  
    contiguous/Int8/unsorted/large     time  6.580 ms  
    contiguous/Int8/unsorted/gigantic  time  68.16 ms  

Results may vary across processors, but you observe results that are 10x
slower, it's probably an issue with the compiler, and please open an issue.

## GHC Specialization Problems

Sadly, the most permissive signature for `sort` causes GHC's specialization
to break. This permissive signature is:

    sort :: (Contiguous arr, Element arr a, Ord a) => arr a -> arr a

And the less permissive variant used by this library is:

    sort :: (Prim a, Ord a) => PrimArray a -> PrimArray a

The latter works nicely with `SPECIALIZE` and `INLINEABLE`, but the former
does not work at all with these. The issue is believed to be related to the
use of an associated constraint type `Element`, which introduced coercions
that might confuse the specializer. However, this has not been confirmed.