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

$\endgroup$
  • 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 '14 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 '14 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 '14 at 16:58
  • 1
    $\begingroup$ @Jukka Suomela: Thanks for the link! I stand corrected. $\endgroup$ – Tsuyoshi Ito Oct 22 '14 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 '15 at 9:58
7
$\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.

| cite | improve this answer | |
$\endgroup$
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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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