2
$\begingroup$

We are all familiar with Bitonic Sort. The computations are predetermined and data-independent.

bitonic sort

Let's say we have a table A = [ 1,3,2,5,6,3,3,21 ]. The output after performing the sort is: A [ 1,2,3,3,3,5,6,21 ].

Observe that we have three entries with value 3 in indexes 1,5, and 6. My question is: After bitonic sort, is this ordered preserved? Meaning the element from index 1 will always appear before the other two, etc.?

$\endgroup$

1 Answer 1

1
$\begingroup$

No.

Consider an input of $n$ ones followed by $n$ zeroes to the bitonic network. This input is only affected by the network in the middle stage, where the order of elements is flipped. Thus the elements do not keep their relative order. Rather, for this input, the order is flipped.

However, the order is not flipped in general. If the input is all zeroes, the entire network is a no-op and the output is equal to the input, preserving the order of bits. Hence the bitonic sorting network cannot be considered stable.

$\endgroup$

Your Answer

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

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