Sorting list (maybe stupid)

Tim Peters tim.one at comcast.net
Wed Jun 12 03:26:18 CEST 2002


[Ken Seehof]
> >>> a = [1,1.0,3.0,3,2.0,2,0,0.0]
> >>> a
> [1, 1.0, 3.0, 3, 2.0, 2, 0, 0.0]
> >>> a.sort()
> >>> a
> [0, 0.0, 1, 1.0, 2.0, 2, 3.0, 3]
>
> So yes, sort() is stable.

No, it's not.

> I suppose it's theoretically possible for a different
> python implementation to use a different sort algorithm,
> but practically speaking, that is very unlikely.

In fact it's almost certain <wink>.  Small lists are handled by binary
insertion sort, for peak speed, and the way that was coded just so happens
to be stable.  That's why small examples will always lead you to believe
.sort() is stable.  The full-blown samplesort used for non-trivial lists
isn't stable and can't be made stable efficiently.






More information about the Python-list mailing list