You can use a binary tree. In each node you store the number of child nodes in the left subtree. (maybe also for the right subtree) If you want to handle duplicates, you could add yet another counter to the nodes.
Finding the median is easy. As a bonus, you can also find the value for *any* rank or percentile. Cost is 2 or3 pointers plus 2 or 3 ints per node, say 20 bytes. If your input is reasonably random, balancing will not be needed. Avoiding dynamic allocation will probably speed things up. (and make deallocation easyer ;-) HTH, AvK _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
