[viff-devel] Bitonic sort

[Martin Geisler]

Hi guys,

I have just implemented a so-called bitonic sort in VIFF. This is a
sorting algorithm which is data-independent -- the comparisons are
fixed beforehand. This makes it good for something like VIFF, I hope.

The code is here:

  http://hg.viff.dk/viff/file/tip/apps/sort.py#l113

and you should compare it to the Java code found here:

  http://iti.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/oddn.htm#section4

It does 466 comparisons to sort 52 numbers (32-bit) and it takes about
4 minutes both share and sort the numbers on thyra{01,02,03} on DAIMI.

-- 
Martin Geisler
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 188 bytes
Desc: not available
URL: <http://lists.viff.dk/pipermail/viff-devel-viff.dk/attachments/20080808/d6bee6d7/attachment.pgp>