"Philippe De Muyter" <address@hidden> writes:
> What's the current output order for "ties" ? Input order ? or
> something else ?
Yes, it's input order. "sort" is stable.
> Does the 'compare' function take care of that ?
No; it returns 0 for ties. It's the caller's responsibility to do the
right thing in that case.
> I had already implemented my ad-hoc test program using a binary heap.
> I will look at splay heaps it you think that could be better.
Douglas Jones reports that they are perhaps the
best for event-queue manipulation in simulations; see
<http://www.cs.wm.edu/~andreas/umsa/presentations/prioqueue.pdf>.
But perhaps it's not worth worrying about this too much;
for our application the performance difference in internal
implementation is probably swamped by the I/O overhead.
> If there's a portable way to detect we overflow a reasonable memory usage,
That part of the code is already present; it's not as portable as we'd
like, but for now let's assume that there's a method that specifies
the approximate maximum amount of memory to use.
> then we could revert to the normal algorithm and output only the first/last
> N lines. Handling the '-u' option should also happen that way.
OK, sounds good.