Referring to this Wikipedia's article: https://en.wikipedia.org/wiki/Sorting_network , with focus on the paragraph Constructing sorting networks.
Can you please explain what Size, upper bound and Size, lower bound (in the table) are?
I would expect that lower bound refers to the minimum connections needed to correctly sort an input of n numbers (am I correct?). If so, why bother with an upper bound? In theory, one could use a number of connections larger than the upper bound so how can it be established?
I have read the linked paper as well (ref. 11) but I am still confused.
The paragraphs after the table give a hint about the meaning of upper bound and lower bound:
For one to ten inputs, minimal (i.e. size-optimal) sorting networks are known, and for higher values, lower bounds on their sizes S(n) can be derived inductively using a lemma due to Van Voorhis: S(n + 1) ≥ S(n) + ⌈log2(n)⌉.
The « upper bound » in the table apparently corresponds to size of the most size-optimal sorting network currently known for a given number of elements to sort. The known size-optimal sorting networks for 1 to 10 elements have been proven to be optimal, but we're not sure that the known size-optimal sorting networks for more elements are actually the most optimal ones. The « lower bound » corresponds to the theorical minimal size of a sorting network to sort a given number of elements: it may be possible that a sorting network of this size does not exists, but we haven't proven that yet.
To sum up:
As a side note I maintain a library with size-optimal sorting networks, and their sizes correspond to the « upper bound » from the table (see also the documentation and the implementation).