a query on sorting

[Scott David Daniels]

Paul McGuire wrote:
>.... In the interests of beating a dead horse into the ground (metaphor-mixing?), 
> I looked at using map to one-line the OP's request, and found an interesting 
> inconsistency.
> 
> I tried using map(reversed, list(enumerate(a))), but got back a list of 
> iterators.  To create the list of tuples, I have to call the tuple 
> constructor on each one, as in:
> 
> map(tuple,map(reversed,list(enumerate(a))))

Doesn't the following read more easily?
     [tuple(reversed(x)) for x in enumerate(a)]

> However, sorted returns a list, not a listsortediterator.  Why the 
> difference in these two builtins?

"sorted" (esp. Timsort) _must_ have the materialized list in memory at
some point in order to sort.  The only alternative would be to provide
a much less efficient heap-based solution that would still need
everything in memory before emitting the first result.  If you always
have to build the list in memory, returning the list gives the recipient
more chances to be efficient.

"reversed" has some great special cases related to "xrange" that can
be accomplished without ever converting the arg to "reversed" to a list.
While "sorted" could be special cased for those cases, the chances of
real useful code containing, "sorted(xrange(a, b, c))" are pretty slim.
If you don't have to build the list in memory, returning a list can make
a program that could be very memory efficient suddenly _much_ less so.

-- 
--Scott David Daniels
scott.daniels at acm.org