Is the bitonic sort algorithm stable? I was wondering, is the bitonic sort algorithm stable? I searched the original paper, 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 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.
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.