6
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ Bitonic sort is a sorting network. Can a sorting network be not stable? How do you define for a sorting network to be stable? $\endgroup$
    – Tsuyoshi Ito
    Oct 22, 2014 at 11:44
  • $\begingroup$ 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? $\endgroup$
    – Tsuyoshi Ito
    Oct 22, 2014 at 11:54
  • 3
    $\begingroup$ @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 hoytech.github.io/sorting-networks pages 27–28. $\endgroup$
    – Jukka Suomela
    Oct 22, 2014 at 16:58
  • 1
    $\begingroup$ @Jukka Suomela: Thanks for the link! I stand corrected. $\endgroup$
    – Tsuyoshi Ito
    Oct 22, 2014 at 21:41
  • 1
    $\begingroup$ @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. $\endgroup$
    – Nobody moving away from SE
    Sep 2, 2015 at 9:58

2 Answers 2

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Patrick Pan
    Feb 13 at 9:01
0
$\begingroup$

It could become stable, but in an inefficient way.

See Is there any efficient Network stable sort (not bubble sort)? which demonstrates it

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.