<p>No, bitonic sort is not stable.</p>

<p>For this post I will denote numbers as 2;0 where only the part before the <code>;</code> is used for comparison and the part behind <code>;</code> to mark the initial position.
Comparison-exchanges are denoted by arrows where the head points at the desired location of the greater value.</p>

<p>As written in the <a href="http://hoytech.github.io/sorting-networks/">link</a> that <a href="https://cstheory.stackexchange.com/questions/27104/is-the-bitonic-sort-algorithm-stable#comment64830_27104">@JukkaSuomela posted</a> a stable sorting network needs to avoid swaps of equal values.</p>

<p>When swapping equal values, the bitonic sorter for two values is already unstable:</p>

<pre><code>0;0 ----- 0;1
      |
      v
0;1 ----- 0;0
</code></pre>

<p>Of course, this can be fixed when we don't swap equal values:</p>

<pre><code>0;0 ----- 0;0
      |
      v
0;1 ----- 0;1
</code></pre>

<p>However, it could happen that the order of two equal elements is swapped without them being compared to each other.</p>

<p>This is exactly the case in this example of a bitonic sorter for 4 values:</p>

<pre><code>1;0 ------ 1;0 ------ 0;2 ------ 0;2
      ^          |          |
      |          |          v
1;1 ------ 1;1 --|--- 1;1 ------ 1;1
                 ||
                 v|
0;2 ------ 0;2 ---|-- 1;0 ------ 1;0
      |           |         |
      v           v         v
2;3 ------ 2;3 ------ 2;3 ------ 2;3
</code></pre>

<p>Although we were careful not to swap elements that compared equal (upper left comparison), the merging pass swapped the order of 1;1 and 1;0 which cannot be corrected later on.</p>

<p>This counterexample proves that bitonic sort cannot be stable.</p>

CC BY-SA 4.0
2023-02-13T09:01:37.617Z
I am afraid the second stage is wrong since a merger network reverses its second input to make the whole concatenated input bitonic. Therefore, the second stage should compare between element 1 and element 4, and element 2 and 3.
Patrick Pan
CC BY-SA 3.0
2015-09-02T09:16:12.077Z
2015-09-02T09:16:12.077Z
Nobody moving away from SE
<p>It could become stable, but in an inefficient way.</p>
<p>See <a href="https://cstheory.stackexchange.com/questions/47098/is-there-any-efficient-network-stable-sort-not-bubble-sort">Is there any efficient Network stable sort (not bubble sort)?</a> which demonstrates it</p>

CC BY-SA 4.0
2020-06-24T17:39:50.170Z
2020-06-30T14:37:38.553Z
2020-06-30T14:37:38.553Z
GM1
<p>I was wondering, is the bitonic sort algorithm stable? I searched the <a href="http://dl.acm.org/citation.cfm?id=808726" rel="noreferrer">original paper</a>, wikipedia and some tutorials, could not find it.</p>

<p>It seems to me that it should be, as it is composed of merge / sort steps, however was unable to find answer anywhere.</p>

<p>The reason why I'm asking - I was comparing <a href="http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/oddn.htm" rel="noreferrer">this particular implementation of bitonic sort</a> to the sort implemented in the C++ standard library, for array length 9 it requires 28 comparison / swap operations, while the standard library sort (which is unstable) requires 25. The three extra cswaps do not seem enough to make the sort stable.</p>

CC BY-SA 3.0
2014-10-22T11:44:57.093Z
[Bitonic sort](http://en.wikipedia.org/wiki/Bitonic_sorter) is a sorting network.  Can a sorting network be _not_ stable?  How do you define for a sorting network to be stable?
Tsuyoshi Ito
CC BY-SA 3.0
2014-10-22T11:54:09.817Z
By the way, I cannot understand the motivation you stated in the last paragraph.  You compared the number of comparisons needed for n=9 between bitonic sort and some unstable sort, and you found that bitonic sort required more comparisons.  How is this related to whether bitonic sort is stable or not?
Tsuyoshi Ito
CC BY-SA 3.0
2014-10-22T12:24:03.820Z
@TsuyoshiIto instinctively, stability seems like something you need to "pay for". so why is stable sort more expensive than unstable one? Sorting network can be unstable, I have come over a peculiar bubble sort implementation (I'm a teacher, I get to see a lots of strange stuff that my students write), which was unstable and thanks to the fixed number of steps it took, it could be implemented as a sorting network. Not practical, but very possible.
the swine
CC BY-SA 3.0
2014-10-22T16:58:09.957Z
@TsuyoshiIto: I also thought that sorting networks would be automatically stable (as a corollary of the 0-1 principle), but it seems that this is not the case. See http://hoytech.github.io/sorting-networks/ pages 27–28.
Jukka Suomela
CC BY-SA 3.0
2014-10-22T21:41:16.030Z
@Jukka Suomela: Thanks for the link!  I stand corrected.
Tsuyoshi Ito
CC BY-SA 3.0
2015-09-02T09:58:06.880Z
@theswine: In `The Art of Computer Programming Vol. 3 Sorting and Searching` Knuth explains that we pay for the uniformity of sorting networks with an increased number of comparisons compared to the optimum.
Nobody moving away from SE
CC BY-SA 4.0
2022-07-15T21:08:55.710Z
Stating the obvious, you can make Bitonic sort stable by appending the port numbers to the sort keys (or array indices in the c++ case.)  Suppose you have items A and B with equal sort keys 50 at indices 7 and 11.   5007 and 5011 will sort A and B in the correct order of A and B (vs B then A)
B Abali
<sorting><sorting-network><stable>
Is the bitonic sort algorithm stable?
the swine
# Is the bitonic sort algorithm stable?

(Asked by: username_0 on 2014-10-18)

I was wondering, is the bitonic sort algorithm stable? I searched the [original paper](http://dl.acm.org/citation.cfm?id=808726), wikipedia and some tutorials, could not find it.

It seems to me that it should be, as it is composed of merge / sort steps, however was unable to find answer anywhere.

The reason why I'm asking - I was comparing [this particular implementation of bitonic sort](http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/oddn.htm) to the sort implemented in the C++ standard library, for array length 9 it requires 28 comparison / swap operations, while the standard library sort (which is unstable) requires 25. The three extra cswaps do not seem enough to make the sort stable.

**Tags:** sorting, sorting-network, stable

> **Comments:**
> **username_1**: [Bitonic sort](http://en.wikipedia.org/wiki/Bitonic_sorter) is a sorting network.  Can a sorting network be _not_ stable?  How do you define for a sorting network to be stable?  
> **username_1**: By the way, I cannot understand the motivation you stated in the last paragraph.  You compared the number of comparisons needed for n=9 between bitonic sort and some unstable sort, and you found that bitonic sort required more comparisons.  How is this related to whether bitonic sort is stable or not?  
> **username_0**: @TsuyoshiIto instinctively, stability seems like something you need to "pay for". so why is stable sort more expensive than unstable one? Sorting network can be unstable, I have come over a peculiar bubble sort implementation (I'm a teacher, I get to see a lots of strange stuff that my students write), which was unstable and thanks to the fixed number of steps it took, it could be implemented as a sorting network. Not practical, but very possible.  
> **username_2**: @TsuyoshiIto: I also thought that sorting networks would be automatically stable (as a corollary of the 0-1 principle), but it seems that this is not the case. See http://hoytech.github.io/sorting-networks/ pages 27–28.  
> **username_1**: @username_2: Thanks for the link!  I stand corrected.  
> **username_3**: @theswine: In `The Art of Computer Programming Vol. 3 Sorting and Searching` Knuth explains that we pay for the uniformity of sorting networks with an increased number of comparisons compared to the optimum.  
> **username_4**: Stating the obvious, you can make Bitonic sort stable by appending the port numbers to the sort keys (or array indices in the c++ case.)  Suppose you have items A and B with equal sort keys 50 at indices 7 and 11.   5007 and 5011 will sort A and B in the correct order of A and B (vs B then A)  

---

## 2 answers

### Answer by username_3 on 2015-09-02. Score: 8 | Accepted answer

No, bitonic sort is not stable.
For this post I will denote numbers as 2;0 where only the part before the ; is used for comparison and the part behind ; to mark the initial position.
Comparison-exchanges are denoted by arrows where the head points at the desired location of the greater value.
As written in the link that @JukkaSuomela posted a stable sorting network needs to avoid swaps of equal values.
When swapping equal values, the bitonic sorter for two values is already unstable:
0;0 ----- 0;1
      |
      v
0;1 ----- 0;0

Of course, this can be fixed when we don't swap equal values:
0;0 ----- 0;0
      |
      v
0;1 ----- 0;1

However, it could happen that the order of two equal elements is swapped without them being compared to each other.
This is exactly the case in this example of a bitonic sorter for 4 values:
1;0 ------ 1;0 ------ 0;2 ------ 0;2
      ^          |          |
      |          |          v
1;1 ------ 1;1 --|--- 1;1 ------ 1;1
                 ||
                 v|
0;2 ------ 0;2 ---|-- 1;0 ------ 1;0
      |           |         |
      v           v         v
2;3 ------ 2;3 ------ 2;3 ------ 2;3

Although we were careful not to swap elements that compared equal (upper left comparison), the merging pass swapped the order of 1;1 and 1;0 which cannot be corrected later on.
This counterexample proves that bitonic sort cannot be stable.

> **Comments:**
> **username_5**: I am afraid the second stage is wrong since a merger network reverses its second input to make the whole concatenated input bitonic. Therefore, the second stage should compare between element 1 and element 4, and element 2 and 3.  

---

### Answer by username_6 on 2020-06-24. Score: 0

It could become stable, but in an inefficient way.

See [Is there any efficient Network stable sort (not bubble sort)?](https://cstheory.stackexchange.com/questions/47098/is-there-any-efficient-network-stable-sort-not-bubble-sort) which demonstrates it


---

