Discrimination sort seems interesting, though couched in such complex terms that it's hard to follow (admittedly, I read the paper[1] instead of watching the vi

Discrimination sort seems interesting, though couched in such complex terms that it's hard to follow (admittedly, I read the paper[1] instead of watching the video). As I understand it, it's a generalized MSD radix sort, and the difference in complexity analysis from traditional pairwise sorts is what the N stands for. For strings, we know that a fixed-size prefix (say a character) that can take on a known finite set of values is capable of discriminating; that is, being a partial order on strings. From this we can construct a radix sort on strings that never has to revisit a character. So the net running time is approximately O(total number of characters in all strings). In contrast, a naive comparison sort may operate in O(nlogn) comparisons, but each comparison has a cost proportional to the length of the string, since we have to re-compare from scratch, such that this works out closer to O(log n * total number of characters in all strings). My recollection is that MSD radix sorts are somewhat space-intensive, especially if we want them to be stable. I think O(n) space is required. Nonetheless, this is very interesting. [1] https://pdfs.semanticscholar.org/7e49/0023f84845c750f4a04b7dca8a0225d3e5d1.pdf https://pdfs.semanticscholar.org/7e49/0023f84845c750f4a04b7d...