Find the optimal sorting network

code-golf sorting

Sorting networks are an abstract model of "wires" carrying numbers, which outputs them sorted.

A comparator in a sorting network works as follows:

This is the optimal sorting network for 4 numbers:

Since there are two kinds of "optimal" sorting networks people care about, we are going for the least number of comparators (those vertical lines).

Given an integer n, output a list of comparators which designates an optimal sorting network for n inputs. The "comparators" are a pair of indices which say which indices in the working array to compare / swap. The indices must be 0-based.

So for the example sorting network, this would be a valid output (viewing 0 as the top wire):

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

As would this:

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

Additionally, any whitespace is ignored (except for tokenizing), and any non-digit is considered whitespace, so this is also a valid output:

0 2 1 3 2 3 0 1 1 2

And also:

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

Furthermore, functions may simply return some iterable that - when flattened - gives the list of numbers in the correct order.

Find the optimal sorting network

code-golf sorting

Sorting networks are an abstract model of "wires" carrying numbers, which outputs them sorted.

A comparator in a sorting network works as follows:

This is the optimal sorting network for 4 numbers:

Since there are two kinds of "optimal" sorting networks people care about, we are going for the least number of comparators (those vertical lines).

Given a non-negative integer n (so yes, 0 and 1 need to be supported), output a list of comparators which designates an optimal sorting network for n inputs. The "comparators" are a pair of indices which say which indices in the working array to compare / swap. The indices must be 0-based.

So for the example sorting network, this would be a valid output (viewing 0 as the top wire):

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

As would this:

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

Additionally, any whitespace is ignored (except for tokenizing), and any non-digit is considered whitespace, so this is also a valid output:

0 2 1 3 2 3 0 1 1 2

And also:

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

Furthermore, functions may simply return some iterable that - when flattened - gives the list of numbers in the correct order.

Find the optimal sorting network

code-golf sorting

Sorting networks are an abstract model of "wires" carrying numbers, which outputs them sorted.

This is the optimal sorting network for 4 numbers (where a vertical line indicates comparison / swap if necessary):

Since there are two kinds of "optimal" sorting networks people care about, we are going for the least number of comparators (those vertical lines).

Given an integer n, output a list of comparators which designates an optimal sorting network for n inputs. The "comparators" are a pair of indices which say which indices in the working array to compare / swap. The indices must be 0-based.

So for the example sorting network, this would be a valid output (viewing 0 as the top wire):

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

As would this:

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

Additionally, any whitespace is ignored (except for tokenizing), and any non-digit is considered whitespace, so this is also a valid output:

0 2 1 3 2 3 0 1 1 2

And also:

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

Find the optimal sorting network

code-golf sorting

Sorting networks are an abstract model of "wires" carrying numbers, which outputs them sorted.

A comparator in a sorting network works as follows:

This is the optimal sorting network for 4 numbers:

Since there are two kinds of "optimal" sorting networks people care about, we are going for the least number of comparators (those vertical lines).

Given an integer n, output a list of comparators which designates an optimal sorting network for n inputs. The "comparators" are a pair of indices which say which indices in the working array to compare / swap. The indices must be 0-based.

So for the example sorting network, this would be a valid output (viewing 0 as the top wire):

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

As would this:

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

Additionally, any whitespace is ignored (except for tokenizing), and any non-digit is considered whitespace, so this is also a valid output:

0 2 1 3 2 3 0 1 1 2

And also:

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

Furthermore, functions may simply return some iterable that - when flattened - gives the list of numbers in the correct order.