list.sort, was Re: [Python-Dev] decorate-sort-undecorate

[Raymond Hettinger]

> [Armin Rigo]
> >> from heapq import *
> >> def isorted(iterable):
> >>     heap = list(iterable)
> >>     heapify(heap)
> >>     while heap:
> >>         yield heappop(heap)
> >>
> > In terms of memory, I think list.sort() always beats the above
> > implementation.
> 
> That can't be -- the heap method only requires a fixed (independent of
N)
> and small amount of working storage.  list.sort() may need to allocate
> O(N)
> additional temp bytes under the covers (to create a working area for
doing
> merges; it can be expected to allocate 2*N temp bytes for a random
array
> of
> len N, which is its worst case; if there's a lot of pre-existing order
in
> the input array, it can sometimes get away without allocating any temp
> space).

The isorted() generator shown above operates on a copy of the data while
list.sort() works in-place.  So, my take on it was the isorted() always
used 2*N while list.sort() used 2*N only in the worst case.


Raymond


#################################################################
#################################################################
#################################################################
#####
#####
#####
#################################################################
#################################################################
#################################################################