Talk:Bitonic sorter

C Implementation Incomplete

The C implementation is missing some crucial portions of the implementations (bitonic merge / sort / swapwith) — Preceding unsigned comment added by 97.81.174.66 (talk) 06:17, 19 March 2012 (UTC)

Why?

The current article doesn't go into the advantages of this sort. Why would you use it?

Secular mind (talk) 11:23, 5 August 2013 (UTC)

Java implementation broken!

The java implementation given throws an array out of bounds exception when run on input of size != 2^k ! Just thought i'd let you know. — Preceding unsigned comment added by 2A01:CB04:62:1400:74F3:3C8:DFC5:1117 (talk) 03:08, 21 March 2016 (UTC)

   I noticed that. I didn't test either algorithm, but by inspection you can see that they only work on inputs of size 2^k. Both algorithms use len/2 for the length of each half at every iteration.  When the total length is odd, that can't be. Is it the case that bitonic sort only works on 2^k arrays? If so, the article definitely should say so. If not, the algorithms need to be fixed.  — Preceding unsigned comment added by 2602:306:3398:DD10:7DAF:AB09:6F9A:588D (talk) 12:07, 6 December 2017 (UTC)

The current C-style pseudocode behaves the same. - Glibg10b (talk) 06:44, 10 December 2021 (UTC)

What is O(log^2 (n)) usually either log sub 2 (n) or log (n^2)?

The top description has an odd big-O notation. Also, if its point is parallelism, it is traditional to use O(n, p) with p being processors. What am I missing? Charles Merriam (talk) 02:14, 22 May 2024 (UTC)

I believe it was intended to represent the multiplicative square of the logarithm, i.e. $(\log n)^{2}$ (note that the most natural confusion here would actually be with the compositional square, i.e. $\log \log n$). I've changed the notation in the article in hopes of averting such confusions (though I may have missed an instance or two so feel free to fix them if you see any). Americanastronaut (talk) 17:42, 27 August 2025 (UTC)

In my opinion $O(nlog^{2}(n))$ is perfectly fine as it can not possible be confused with $O(nlog(n^{2}))$ and it can not be $O(nlog(log(n)))$ because the lower bound of comparison based sort algorithms is $O(nlog(n))$ MrTroble (talk) 10:28, 3 September 2025 (UTC)

I agree that the "risk" of confusion here is generally very low, but IMHO on a site like Wikipedia it is probably best not to assume the reader will correctly disambiguate the notation by reasoning from things like lower bounds on complexity ;) Americanastronaut (talk) 22:41, 6 September 2025 (UTC)

IMO the $O((log(n))^{2})$ or $O(log(n)^{2})$ is harder to read but that might just be me being used to the other notation. I see your point and thank your for your contribution. I just wanted to add the above reason why I picked the notation to the discussion. MrTroble (talk) 08:01, 8 September 2025 (UTC)

Confusion about assumptions on bitonic input

In the initial description of the bitonic sorter, there seems to be an operating assumption (particularly evidenced by statements like "the first half of the input sequence is compared against the last half of the input sequence. Both subsequences are already monotonically decreasing or increasing, respectively" which occurs in the discussion of the recursive construction diagram) that the input sequence is not only bitonic but that it can be obtained as the concatenation of a non-decreasing sequence of length exactly $n/2$ followed by a non-increasing sequence also of length exactly $n/2$. This is a strictly stronger condition than bitonicity as defined in the lead, and it also appears not to be used in the section proving correctness; I imagine it was just included by mistake, but I haven't combed through the whole article (nor the sources) thoroughly enough to be confident in fixing it myself, so I'll leave this here for now. Americanastronaut (talk) 17:37, 27 August 2025 (UTC)

Yes, good catch that is a special case which is not the case in general. I have badly worded this sentence so I will remove it. MrTroble (talk) 10:19, 3 September 2025 (UTC)