[Python-bugs-list] [ python-Bugs-412500 ] Unstable sort

[noreply@sourceforge.net]

Bugs item #412500, was updated on 2001-03-30 07:01
You can respond by visiting: 
http://sourceforge.net/tracker/?func=detail&atid=105470&aid=412500&group_id=5470

Category: Python Library
>Group: Not a Bug
>Status: Closed
Priority: 5
Submitted By: Tomasz Kowaltowski (kowaltowski)
Assigned to: Nobody/Anonymous (nobody)
Summary: Unstable sort

Initial Comment:
The "sort" method for sequences uses an unstable
algorithm, ie, elements with equal keys may have their
original order not preserved.  It isn't exactly a bug,
but it can be annoying.  It seems that most sort
utilities are stable.

I am using:

   Python 2.0 (#1, Mar  1 2001, 15:35:16) 

-- Tomasz Kowaltowski

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

>Comment By: Tim Peters (tim_one)
Date: 2001-03-30 12:12

Message:
Logged In: YES 
user_id=31435

This is functioning as designed, and no practical variant 
of quicksort or samplesort is stable.  I tried a dozen 
implementations of stable algorithms for list.sort(), but 
they were all significantly slower and/or more space-
consuming than the samplesort/binary-insertion hybrid 
Python uses.

Most apps simply don't care about stability, so by default 
Python shouldn't make people pay extra for it.  If your 
apps do care, you can take your sequence x and apply .sort
() to the derived sequence

zip(x, range(len(x)))

instead.  No two elements in the derived list compare 
equal, and because comparison of tuples is done 
lexicographically, tagging each original element with its 
original index preserves the original order of equal 
original elements.

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

You can respond by visiting: 
http://sourceforge.net/tracker/?func=detail&atid=105470&aid=412500&group_id=5470