4 ms·

What's the catch? Are there any preconditions on the input required?

KirinDave 9y ago
No. The catch is that it's hard to write it in a way that doesn't require very fiddly local mutation or explosive allocation. The other catch is that no one has demonstrated that you can do it without a good static type system. It shouldn't be impossible, but there are a lot of challenges in an already challenging algorithm.
gbacon 9y ago
What are the constants hiding inside that 𝒪(𝑛)?
- KirinDave 9y ago
  They can be bad. But so was merge sort in its naive implementation and folks worked that out. Radix sort sees a lot of use in the real world and it saves a lot of energy.
kraghen 9y ago
All orderings must be specified as a reduction to a primitive order using the fact that if you have an equivalence relation on some type A and a reduction f : B -> A then you have an equivalence on B defined by x = y when f(x) = f(y). Now, take the rational numbers. For the usual binary comparison we can simply define (a/b) < (c/d) as ad < cb. It's not obvious how to express this as a reduction to a primitive ordering (the answer is to compute the continued fraction). In fact, I'm not aware of any systematic way of deriving discrimination-suitable orderings from binary predicates -- it might be an open research problem, as far as I am aware.
- KirinDave 9y ago
  > In fact, I'm not aware of any systematic way of deriving discrimination-suitable orderings from binary predicates -- it might be an open research problem, as far as I am aware. That'd be an even more remarkable discovery in light of the stuff you worked on though, wouldn't it?
  - kraghen 9y ago
    It might, I never really discussed this aspect with Fritz! For my thesis I was mostly focussed on applications to database queries, and I never encountered any concrete examples of orderings that couldn't be dealt with in an obvious way using discrimination based sorting.

No. The catch is that it's hard to write it in a way that doesn't require very fiddly local mutation or explosive allocation. The other catch is that no one has demonstrated that you can do it without a good static type system. It shouldn't be impossible, but there are a lot of challenges in an already challenging algorithm.

gbacon 9y ago

What are the constants hiding inside that 𝒪(𝑛)?

KirinDave 9y ago
They can be bad. But so was merge sort in its naive implementation and folks worked that out. Radix sort sees a lot of use in the real world and it saves a lot of energy.

kraghen 9y ago

All orderings must be specified as a reduction to a primitive order using the fact that if you have an equivalence relation on some type A and a reduction f : B -> A then you have an equivalence on B defined by x = y when f(x) = f(y). Now, take the rational numbers. For the usual binary comparison we can simply define (a/b) < (c/d) as ad < cb. It's not obvious how to express this as a reduction to a primitive ordering (the answer is to compute the continued fraction). In fact, I'm not aware of any systematic way of deriving discrimination-suitable orderings from binary predicates -- it might be an open research problem, as far as I am aware.

KirinDave 9y ago
> In fact, I'm not aware of any systematic way of deriving discrimination-suitable orderings from binary predicates -- it might be an open research problem, as far as I am aware. That'd be an even more remarkable discovery in light of the stuff you worked on though, wouldn't it?
- kraghen 9y ago
  It might, I never really discussed this aspect with Fritz! For my thesis I was mostly focussed on applications to database queries, and I never encountered any concrete examples of orderings that couldn't be dealt with in an obvious way using discrimination based sorting.