Sorting Network

A predefined list of comparision and swaps that sort a list of fixed size. (See section 7.6 in Let Over Lambda)

E.g. For a list of 3 elements, the following comparision and swaps will sort the list:

1. (0, 1)
2. (0, 2)
3. (1, 2)

Similarly, this will sort the 3 elements too:

1. (0, 2)
2. (0, 1)
3. (1, 2)

Some sorting newtorks are better than other in terms of number of comparision and swaps they perform. For example the latter network for n=3 is better than the former. i.e. If we assume uniform distribution of all permutations of three numbers then the latter newtork will do less number of swaps on average.

Optimal sorting newtork for some n have been found but finding optimal sorting network for any n is still an open problem.