Rough analysis: If the problem is general, keeping a list sorted is the equivalent of inserting the members into a priority queue, which is O(n lg n) (for a binary heap) going in and O(n) walking the tree if you have access to the internal tree structure (vs calling a get-min function that rebalances the tree over and over). Non-general data (known bounds, etc) can be inseted into a sorted data structure in less time. Creating a list and then sorting it is O(n) for the list creation, then a theoretical O(n lg n) for the sort (although possibly less (expected case) in practice depending on the data and algorithm used), after which the items can be read in O(n). The problem with that is that, unless the data size is known, the list must be constructed as a list and not an Array, which means that the sort itself can be very slow (or adds another O(n) conversion step from List to Array). Final tally seems to very slightly favor the priority queue if it gives you enough access to walk the sorted tree and you can create the tree from a stream source of some sort. If you already have the data in an Array, then an in-place sort is likely to win. -David On 8/19/06, jean-david hsu wrote: > > Just wondering on the average if it is more efficient to take time to > keep a list sorted as we insert or simply sort the list at the end? > > JD Hsu > > > p5.vert.ukl.yahoo.com uncompressed Sun Aug 20 03:27:01 GMT 2006 > > > > ___________________________________________________________________________ > D�couvrez un nouveau moyen de poser toutes vos questions quelque soit le > sujet ! > Yahoo! Questions/R�ponses pour partager vos connaissances, vos opinions et > vos exp�riences. > http://fr.answers.yahoo.com > > _______________________________________________ > Caml-list mailing list. Subscription management: > http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list > Archives: http://caml.inria.fr > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs >