[erlang-questions] Re: Priority queues and Erlang

[Benjamin Johnston]

> > I suspect the real situation is that Abrash only used the bubble 
> > sort on data that was already sorted or just a swap or two away 
> > from being sorted.
>
> Er, no.  The vertex data is completely replaced every frame.

So I dug out my copy of Abrash's Graphics Programming Black Book, and it had
this to say about bubble sorting (this being the only reference to bubble
sorting in the index):

"Listing 40.1 uses a bubble sort, usually a poor choice for performance.
However, bubble sorts perform well when the data are already almost sorted,
and because of the X coherence of edges from one scan line to the next,
that's generally the case with the AET. An insertion sort might be somewhat
faster, depending on the state of the AET when any particular sort occurs,
but a bubble sort will generally do just fine.

An insertion sort that scans backwards through the AET from the current edge
rather than forward from the start of the AET could be quite a bit faster...
I've chosen [against this] partly to minimize memory requirements... The
main reason, though, is the potential rewards for the complication of back
links and insertion sorting aren't great enough: profiling a variety of
polygons reveals that less than 10 percent of time is spent sorting the
AET."

(Special Edition, p755)

It seems that Abrash's claims also support Richard's data.

-Ben