[issue25792] sorted() is not stable given key=len and large inputs

[Sam Obstgarten]

New submission from Sam Obstgarten:

Tested under MacOS 10.11.1
Python 2.7.8

When using sorted() with key=len, sorted() is not stable (i.e. it does not return the same sorting depending on the input file). I expected, that sorted() sorts (i) first according the string length and then (ii) alphabetically.

I used as input Bitcoin addresses (Base58 encoding). First with 1 million Bitcoin addresses, and then with only 9. The results of the last addresses differ in their respective order.

1) Test with 1 million addresses, and these are the last ones:

[...]
1W7ezLRaahQTRfgxwZjkyFASPqMcskeMi
1Jf5QEDgpdPYmj8VwKWcTQonwZqSfMvhA
1MttkWDPEgGRPrEfYD3awWfijWcKw6QJL
1QrH9dJexkL78T12B6LVm4yctFhFJS4S3
1pdbjAiEKVxUc1fudq3HtPzkxQxPxYxuN
1NgahguJexVUmW3FFhS4vQbfRkGHfbSn2
1111111AgxDnb8UWCwZnJGUNrX6cAzaL
11111116Jvg5YivHHTcuapzk5CtSEBVA
1111111111111111111114oLvT2

2) Test with only these 9 addresses:

1W7ezLRaahQTRfgxwZjkyFASPqMcskeMi
1QrH9dJexkL78T12B6LVm4yctFhFJS4S3
1pdbjAiEKVxUc1fudq3HtPzkxQxPxYxuN
1Jf5QEDgpdPYmj8VwKWcTQonwZqSfMvhA
1MttkWDPEgGRPrEfYD3awWfijWcKw6QJL
1NgahguJexVUmW3FFhS4vQbfRkGHfbSn2
1111111AgxDnb8UWCwZnJGUNrX6cAzaL
11111116Jvg5YivHHTcuapzk5CtSEBVA
1111111111111111111114oLvT2

I can provide more details and the full set of Bitcoin addresses if required.

----------
components: Interpreter Core
messages: 255840
nosy: Sam Obstgarten
priority: normal
severity: normal
status: open
title: sorted() is not stable given key=len and large inputs
type: behavior
versions: Python 2.7

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue25792>
_______________________________________