Is there any efficient Network stable sort (not bubble sort)?

Question

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

Answer 1

It depends on the exact restrictions of the problem. Strictly speaking, a sorting network can only make use of comparators on the data, so given that the network needs to potentially disambiguate an additional log(N) bits, I wouldn't count on there being a practical stable sorting network with fewer than O(log^3 N) nodes.

However, if you are sorting integers the solution shouldn't be a problem provided you have log n bits to spare. Otherwise you can double the size of the word.

void SortStable(int * array, const int N) {

    const int LOGN = ulog2(N-1);

    for (int i=0; i<N; ++i) array[i] = (array[i]<<LOGN) ^ i;

    SortUnstable(array, N);

    for (int i=0; i<N; ++i) array[i] >>= LOGN;
}

where ulog2(n) returns the index of the highest set bit of n, which can be computed in one instruction in some architectures or implemented in a number of ways.

If you can't compare bits directly because your comparison operator is not trivial then using a comparison network is most likely the wrong approach to begin with, given that you probably have some kind of class or structure with multiple fields and/or non-trivial copy operator, and moving the data around O(log^2 N) times per item will ruin performance anyways. In that case you could always create an index array and sort that instead.