(replying to an old thread from august).

Looking at this from a functionaly point of view, 
sorting dependencies is naturally done through a topological sorting.

And topological sorting does not preserve anything from the input
(which is a set of pairs).

This is one feature I added in OpenBSD's tsort:
     -h file
             Use file, which holds an ordered list of nodes, to resolve ambi-
             guities.  In case of duplicates, the first entry is chosen.


Since then, the dependency engine in our ports tree has been reengineered 
to basically output list of pairs suitable for tsort, and we've got at
least one script that takes a list of packages, and sorts it so that 
dependencies occur first, but also using the initial list as a hint file,
and thus the result is not disturbed all that much compared to the initial
list.
(that's ports/infrastructure/build/check-plist).

Works quite well, in case you wish to follow that route.