Ok, I realize Bitonic sort is not stable and any attempt to make it stable is inefficient, or is there some efficient way?

But is there some other network sort which is indeed stable beside bubble sort which is O(N*N)?

Stability definition could be found at https://en.wikipedia.org/wiki/Sorting_algorithm as:

Stable sort algorithms sort repeated elements in the same order that they appear in the input

The key of making any sort as stable is also there as:

Unstable sorting algorithms can be specially implemented to be stable. One way of doing this is to artificially extend the key comparison, so that comparisons between two objects with otherwise equal keys are decided using the order of the entries in the original input list as a tie-breaker

For Bitonic sort it would be:

if ((a[i].data == a[j].data) &&
    (((ASCENDING == true) &&
    (((!dir) && a[i].index < a[j].index) || (dir && a[i].index > a[j].index)))
    (((ASCENDING == false) &&
        (((!dir) && a[i].index > a[j].index) || (dir && a[i].index < a[j].index))))))
    exchange(a, i, j);

a[].data is your data, a[].index is your indices and dir=true for Ascending order
and exchange is the exchange function

But this is not so efficient way especially if you have input indices besides the sorted data, which is not in linear order and then you need to perform Gather after Sort

  • $\begingroup$ Can you include stability definition? $\endgroup$
    – VS.
    Jun 24, 2020 at 3:15


Your Answer

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

Browse other questions tagged or ask your own question.