csortingswapsorting-network

Sorting Network SWAPs for 64 elements

I am trying to use Sorting Network in a C program to sort a small list A of n elements. A Sorting Network consists of SWAP(x, y) macros, each of which compares two elements A[x] and A[y], and swaps if necessary. This website generates the sequence of SWAP(x, y) macros for sorting n <= 32 elements.

Now, I am looking for the SWAP(x, y) sequence for sorting n = 64 elements. At this point, I am not sure if Sorting Network would be faster than using other sorting algorithms for n = 64 elements, but I wish to test it. My question is: is there any website/paper/project that lists this sequence? Or is there any algorithm to generate for n = 64 from the Sorting Networks for n <= 32?

Thanks.

Solution

  • This is related to shifting a circular array (Approach #3 in https://leetcode.com/articles/rotate-array/# )

    There are algorithms to determine the sequence i.e. Bose-Nelson algorithm (https://metacpan.org/pod/Algorithm::Networksort), a C implementation is in https://github.com/atinm/bose-nelson/blob/master/bose-nelson.c