search

jgamble / Algorithm-Networksort

Release history of Algorithm-Networksort
https://metacpan.org/release/Algorithm-Networksort
Other
13 stars 4 forks source link

Practical application of SNs #22

Open hoytech opened 6 years ago

hoytech commented 6 years ago

Sorry I'm using this issue tracker as a place to dump cool links; maybe we should make some kind of wiki page?

Anyway see appendix S in the following paper: https://ntruprime.cr.yp.to/ntruprime-20170816.pdf

It describes a vectorised implementation of an n=32 merge-exchange net used for constant-time sorting. I have some more info on constant time applications in slides 31-33 of my (now pretty dated) presentation:

https://hoytech.github.io/sorting-networks/#slide31

jgamble commented 6 years ago

It's good. At the moment I view these as requests for implementations, which I definitely need to start on (two projects in the way right now). But a wiki page that listed the different types of sorting networks would be a good idea.

As long as we're on the subject, I acquired a book I never knew existed: Designing Sorting Networks, by Al-Haj Badder & Batcher. You may recognize their names.

hoytech commented 6 years ago

Hehe yes I recognise them. I never got a copy of the book but I found a PDF of Baddar's PhD thesis online which I think had a lot of the same material.

hoytech commented 6 years ago

DJB just released a sort-of general purpose implementation:

https://sorting.cr.yp.to/