Re: Binqry Tree sort

nejla.ghaboosi@xxxxxxxxx wrote: 

We have an unsorted set like  S. We put the elements of the set
sequentially on the leaves on a conplete binary tree. I'm looking for
an algorithm to sort the set S with this binary tree structure. The
result should be available on the leaves of the tree again.
Example:
S = {5, 2, 3, 1}

Initial Tree:
          ______
        /        \
      __         __
     /   \     /    \
    5     2   3      1

final Tree: 
>           ______
>         /        \
>       __         __
>      /   \     /    \
>     1     2   3      5

any ideas?

This smells suspiciously like an attempt to patch an unsuitable attack on a problem. What is the real problem? Note that the initial tree is inefficient, in that it does not use the interior nodes at all, and it cannot be built dynamically.

It might well be that you would be better off inputting the data into a linked list, and sorting that. Mergesort is very efficient for this. But the suitability depends on your actual problem.

BTW, use neither tabs nor proportional spacing in USENET postings. Also read my sig below and the URL _before posting again_.

--
"If you want to post a followup via groups.google.com, don't use
 the broken "Reply" link at the bottom of the article.  Click on
 "show options" at the top of the article, then click on the
 "Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
.