How to sort an unsorted binary leaf tree in parallel in haskell? [duplicate]

Possible Duplicate:

Can I represent a Red-black tree as binary leaf tree?

The following is just an example of small binary leaf tree with items in the leaves only and they are not sorted. Without flattening the tree, and then sorting it before building a sorted tree again, is there a way to sort it in parallel (using par and seq primitives). e.g. sort the left and right branches开发者_开发百科 in parallel then do a final sort on these two.

       /\
      /  \
     /    \
    /\    /\
   /  \  /  \
   3  1  5  2

To say "without flattening" is meaningless, as the tree has to be deconstructed and reconstructed anyway: Even in your simple example every single node must be changed, so you can't save anything from the existing structure. Read the tree, perform a suitable sorting algorithm (merge sort seems to be a good choice here, especially it works well with parallel computation) and reconstruct the tree. There is no better way.