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.
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. $\endgroup$