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);
}
When:
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