Description
This is another long-term proposal: the searchsorted suite of functions in sort.jl can be improved. The current implementations have several problems:
(1) If the user specifies a custom sort order for sorting, say ord1, he/she has to remember to use that order ord1 every time he/she calls searchsorted, otherwise those routines will silently fail (return the wrong answer)
(2) There is a performance issue: if the user specifies a custom sort order via lt= or by=, then the compiler cannot inline the lt and by functions, so they have to be called via function pointers in the inner loops, and in fact, the dispatch has to be done again each time they are called.
Fortunately, there is a straightforward solution to all of these problems, namely, create a type OrderedVect{T,Ord} whose constructor sorts the data and doesn't allow changes (so that the sort-order invariant is guaranteed). The sort order is hard-coded into the OrderedVect type at compile time so that the lt and by functions can be inlined and the user doesn't have to worry about remembering them.