Re: Binqry Tree sort

nejla.ghaboosi@xxxxxxxxx wrote:
) To Willem:
)> Mergesort or quicksort won't work because they have a sequential stage
)> that is O(n) and unparallelizable.
)
) They are parallelizable. I read about their parallel implementation.

As far as I know, the final 'merge' step isn't parallelizable.
That's an O(n) step, and that's what I meant. You can do the other
steps in parallel, but the final step has to be done on one processor,
because each step depends on the result of the previous step.

)> Basically, the root node is a huge bottleneck.
)
) The root node has no bottle neck becasue it just receives data from its
) 2 children not more than that. And all data go from each tree level to
) the next level, upward or downward, step by step & synchronously. Think
) about the pipeline idea of computer architectures of Super-Scalars .

Maybe you didn't understand why it is a bottleneck:

Suppose you have a string that is in reversed sorting order, and your
network sorts it. Each piece of data will then have to pass through the
root node to the other half of the tree. So that's n pieces of data
having to pass through, making it the bottleneck, and restricting your
running time to O(n).


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
.