[Patches] [ python-Patches-1080078 ] list sort is not "in place"

[SourceForge.net]

Patches item #1080078, was opened at 2004-12-06 19:15
Message generated for change (Comment added) made by shd
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=1080078&group_id=5470

Category: Documentation
Group: Python 2.4
Status: Closed
Resolution: Rejected
Priority: 5
Submitted By: Heikki Orsila (shd)
Assigned to: Nobody/Anonymous (nobody)
Summary: list sort is not "in place"

Initial Comment:
list sort method says the sort algorithm is "in place",
but it is not. It requires O(N) extra memory at worst
case. A patch is attached that corrects the
documentation in Objects/listobjects.c.




----------------------------------------------------------------------

>Comment By: Heikki Orsila (shd)
Date: 2004-12-07 15:39

Message:
Logged In: YES 
user_id=6941

My bad. Sorry for misunderstanding the meaning of in-place.


----------------------------------------------------------------------

Comment By: Raymond Hettinger (rhettinger)
Date: 2004-12-06 19:49

Message:
Logged In: YES 
user_id=80475

Sorry, the patch is not right.  In-place is meant to
communicate thet the original list is mutated.  Contrast
that with the behavior of sorted() which leaves the original
intact.

Perhaps you are thinking in terms of heapsort which is
in-place and requires no additional auxiliary storage. 
While that is not true for the current algorithm, we do not
document or make promises about the memory requirements --
that is considered to be an implementation detail that is
subject to change.

----------------------------------------------------------------------

Comment By: Tim Peters (tim_one)
Date: 2004-12-06 19:48

Message:
Logged In: YES 
user_id=31435

Sorry, I'm rejecting this.  Of course it's "in place":  x.sort() 
does not return a new list.  Its only visible effect is to 
permute the elements of x.  That's what "in place" means.

That the current implementation may require temp memory is 
irrelevant to that, and *because* it's an internal 
implementation detail, doesn't belong in the docstring.  
The "in place" was added to the docstring because many 
newcomers believed x.sort() left x alone, and returned a new 
list in sorted order (which is what the new-in-2.4 sorted() 
builtin does).

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=1080078&group_id=5470