3 ms·
(Kind of a tangent, but if you're into sorting check out: "Generic top-down discrimination for sorting and partitioning in linear time" https://www.cambridge.
by carapace 8y ago
(Kind of a tangent, but if you're into sorting check out:
"Generic top-down discrimination for sorting and partitioning in linear time"
https://www.cambridge.org/core/journals/journal-of-functional-programming/article/generic-topdown-discrimination-for-sorting-and-partitioning-in-linear-time/B85E48EFC0B4D2BDDDE9A3885094FDD7 https://www.cambridge.org/core/journals/journal-of-functiona...
Abstract: "We introduce the notion of discrimination as a generalization of both sorting and partitioning, and show that discriminators (discrimination functions) can be defined generically, by structural recursion on representations of ordering and equivalence relations. Discriminators improve the asymptotic performance of generic comparison-based sorting and partitioning, and can be implemented not to expose more information than the underlying ordering, respectively equivalence relation. For a large class of order and equivalence representations, including all standard orders for regular recursive first-order types, the discriminators execute in the worst-case linear time. The generic discriminators can be coded compactly using list comprehensions, with order and equivalence representations specified using Generalized Algebraic Data Types. We give some examples of the uses of discriminators, including the most-significant digit lexicographic sorting, type isomorphism with an associative-commutative operator, and database joins. Source code of discriminators and their applications in Haskell is included. We argue that built-in primitive types, notably pointers (references), should come with efficient discriminators, not just equality tests, since they facilitate the construction of discriminators for abstract types that are both highly efficient and representation-independent.")
- KirinDave 8y agoI've tried so many times to frontpage that, but I've failed. Maybe we should have another go? Nothing in djbsort's approach is inapplicable to another sorting algorithm, so maybe we can hope for better primitive support for discrimination sort implementations (or at least american flag sort implementations). I seem to recall reading that discrimination sorts are inherently content-independent.