Talk:Sorting network

Updates

I'm doing some major updates to this article. The draft can be found at User:Oskar Sigvardsson/Sorting networks. More updates are coming. You got any questions, just ask --Oskar 00:26, 26 March 2008 (UTC)

Applications

Hello, can you tell me, if/where in practice sorting networks are used? Maybe an electrical engineer can affirm here that his company uses hardware chips in aircraft industry for sorting :) —Preceding unsigned comment added by 89.247.15.59 (talk) 15:07, 23 January 2010 (UTC)

The theory is also useful in software. Parallellism influences single-core computations, since you want to avoid dependencies between sequential computations. The static structure can allow an implementation without branches (jumps) as well. -- Sverdrup (talk) 11:08, 19 December 2011 (UTC)

I added a reference for the use in GPGPU, which means compiling a sorting net to CUDA or OpenCL code which is then executed on a GPU. QVVERTYVS (hm?) 15:48, 26 September 2014 (UTC)

Fourier / History

Isn't it true that sorting networks were invented by analyzing the steps in the FFT? Should this be in the history section? There is currently no history section. — Preceding unsigned comment added by 76.111.60.215 (talk) 23:26, 26 May 2011 (UTC)

There's a short remark in Batcher's 1968 paper that calls the reader's attention to a similarity with the FFT. QVVERTYVS (hm?) 13:32, 26 September 2014 (UTC)

Reverse comparators?

The examples all have the property that, for each comparator between wires i and j, if i < j then the smaller value goes to wire i and the greater value to j. But is this necessarily the case, either

1. in order for it to be called a sorting network?
2. in order for it to be optimal in size?
3. in order for it to be optimal in depth?

Since there's no mention of this requirement I take it that this criterion isn't necessary for 1. But I can imagine that for some input sizes an optimal network might temporarily put some pairs of elements out of order. Has this been studied in depth? It would be good if we could find some information on it rather than ignoring the possibility as the article effectively does at the moment. — Smjg (talk) 15:19, 12 April 2014 (UTC)

This is not yet in the article, but sorting networks are comparison sorts. I.e. they have to order their inputs according to some total order. Networks that don't sort are called comparison networks by Cormen et al.. Non-sorting comparison networks include min/max-finding networks and median networks; there's some literature about this, but it's hard to find and poorly cited. I can dug up some references if you like.

Re: temporarily placing elements out of order, I've only just started reading up on sorting networks, but it seems like there's no requirement that a sorting net should sort its input incrementally, i.e. data should become "more sorted" over time (that notion can be made precise if needed, but I haven't encountered it in the context of sorting nets so far). QVVERTYVS (hm?) 13:38, 26 September 2014 (UTC)

The property is not actually a limitation. Any network of correctly connected comparators (i.e. a network where each signals has fan-in 1 and fan-out 1 and there are no oriented loops) can be redrawn as a network satisfying the condition, maybe with some permutation of outputs. To do the transformation, just assign already sorted values 1...n to inputs and compute all intermediate and output signals. Then if a comparator has inputs (and outputs) marked i and j, then draw it on the ith and jth wires, keeping the order of comparators. -- M. G. J. (talk) 04:19, 22 September 2015 (UTC)

External Link 'List of Sorting Networks'

This link goes to an old, pre-HTML5 web page that runs an ancient version of a module that creates sorting networks (I should know; I'm the author of both the page and the module). I'm startled that the page is still there, quite frankly.

I highly recommend that this entry be removed, and possibly replaced with a link to the up-to-date module's CPAN page (<http://search.cpan.org/perldoc?Algorithm::Networksort>) or MetaCPAN page (<https://metacpan.org/pod/Algorithm::Networksort>).

I'd do it myself, but I suspect that modifying references to my own code might violate some rule (however, I'll do it if we're well into 2018 and there's no response). John Gamble (talk) 00:23, 12 December 2017 (UTC)

Corrections of Feb 15, 2020

1. Regarding Van Voorhis lemma: its form S(n + 1) ≥ S(n) + ⌈log₂n⌉ (as cited by Codish et al.) is a bit weak; I replaced it by a stronger variant what Knuth gives (vol. 3, p. 240, exercise 42): S(n) ≥ S(n − 1) + ⌈log₂n⌉. The difference is essential for cases like S(9) ≥ S(8) + 4 (not "+3"), S(17) ≥ S(16) + 5 (not "+4") etc. To verify that Codish et al. actually were using the stronger variant, note that they (in the table on page 3) show "old lower bound" S(9) ≥ 23, not 22, as if their form of inequality were in use (given S(8) = 19).
2. Their "new lower bounds" from the same table (S(9) ≥ 25, S(10) ≥ 29, S(11) ≥ 33, S(12) ≥ 37, S(13) ≥ 41, S(14) ≥ 45, S(15) ≥ 49, S(16) ≥ 53) are based by their main result S(9) = 25 and the Van Voorhis lemma (for S(10) and so on). But now these bounds (starting from S(11)) are obsolete as it was proven that S(11) = 35 instead of 33. I did corresponding updates. -- M. G. J. (talk) 18:49, 15 February 2020 (UTC)

Incorrect statement of my result

Currently the article states "An optimal network for size 11 was found in December of 2019 by Jannis Harder, which also made the lower bound for 12 match its upper bound", linking to my result on Github. That is not my result though. Networks matching the optimal size bound for 11 and 12 channels were known before (e.g. see http://users.telenet.be/bertdobbelaere/SorterHunter/sorting_networks.html), that's also where the upper bounds come from. I also state this in the readme of the linked repository. What I did was proving that no smaller networks exist, thereby showing that those already known networks are indeed optimal, which was only conjectured before.

Given the policy against contributing original research, I'm not sure if I should correct this myself, but would appreciate if someone can look at the prior publications of sorting networks matching the bound and correct the article accordingly. Jannis "jix" Harder (talk) 10:52, 28 March 2020 (UTC)

After remembering this and seeing that it still wasn't corrected almost 3 years later, I read a bit more about Wikipedia's policies and came to the conclusion that correcting the already existing citation I didn't add is probably not violating WP:SELFCITE and also is a slight improvement regarding WP:SPS, so I went ahead and made that change myself. Jannis "jix" Harder (talk) 13:36, 28 February 2023 (UTC)

Label of the first diagram of a sorting network is wrong

The Label states the following: "A simple sorting network consisting of four wires and five connectors". This is incorrect, because a wire in the context of sorting networks is the connection between two comparators or one comparator and an input/output of a sorting network.

"Note that a line does not represent a single wire, but rather a sequence of distinct wires connecting various comparators."

So this network actually has 14 wires and 4 lines.

References

Transformations on sorting networks

Is there any research on what transformations can be performed on sorting networks while still yielding valid sorting networks? Like, how to rearrange the rows without breaking it, or how to cull some rows? I know, at least, how to delete the highest or lowest row (simply remove it altogether and throw away the comparators), but can this be achieved with internal rows? And are there predictable rearrangements of internal comparators? --Pish1le (talk) 05:46, 4 November 2022 (UTC)