4 ms·
We already have both a radix sort[0] and a bitonic merge sort[1]. They perform alright - nothing world-shaking, but fine. I was more interested in whether str
by Athas 9y ago
We already have both a radix sort[0] and a bitonic merge sort[1]. They perform alright - nothing world-shaking, but fine. I was more interested in whether string sorting has some particularly clever algorithms.
[0]: https://github.com/diku-dk/futhark/blob/master/futlib/radix_sort.fut https://github.com/diku-dk/futhark/blob/master/futlib/radix_...
[1]: https://github.com/diku-dk/futhark/blob/master/futlib/merge_sort.fut https://github.com/diku-dk/futhark/blob/master/futlib/merge_...
- amelius 9y agoNice to see that you have radix-sorting covered! I'm not aware of sorting algorithms that use "clever" tricks; the challenge with sorting seems to be in the low-level optimization (e.g. making sure that no unnecessary data-copying takes place). If you are looking for a challenge, then you could try sorting arbitrary length strings (more difficult since the comparison operator is of non-constant time). Or do something like the Burrows-Wheeler transform [1], where you sort all rotations of a very large string. This is actually a very useful operation for building a large search index [2]. Many people in e.g. bioinformatics would be very interested in a fast solution. [1] https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transf... [2] https://en.wikipedia.org/wiki/FM-index https://en.wikipedia.org/wiki/FM-index