`sorted()` is not stable

[GimmickNG]

The sorted() function is not stable. Example:

>>> ids = [{"i": 0, "id": "ID: {0}".format(i)} for i in range(10)]
>>> ids
[{'i': 0, 'id': 'ID: 0'}, {'i': 0, 'id': 'ID: 1'}, {'i': 0, 'id': 'ID: 2'}, {'i': 0, 'id': 'ID: 3'},
{'i': 0, 'id': 'ID: 4'}, {'i': 0, 'id': 'ID: 5'}, {'i': 0, 'id': 'ID: 6'}, {'i': 0, 'id': 'ID: 7'},
{'i': 0, 'id': 'ID: 8'}, {'i': 0, 'id': 'ID: 9'}]
>>> sorted(ids, key=lambda obj: obj['i'])
[{'i': 0, 'id': 'ID: 6'}, {'i': 0, 'id': 'ID: 5'}, {'i': 0, 'id': 'ID: 9'}, {'i': 0, 'id': 'ID: 7'},
{'i': 0, 'id': 'ID: 8'}, {'i': 0, 'id': 'ID: 1'}, {'i': 0, 'id': 'ID: 0'}, {'i': 0, 'id': 'ID: 4'},
{'i': 0, 'id': 'ID: 2'}, {'i': 0, 'id': 'ID: 3'}]

In CPython:

>>> ids = [{"i": 0, "id": "ID: {0}".format(i)} for i in range(10)]
>>> ids
[{'i': 0, 'id': 'ID: 0'}, {'i': 0, 'id': 'ID: 1'}, {'i': 0, 'id': 'ID: 2'}, {'i': 0, 'id': 'ID: 3'}, 
{'i': 0, 'id': 'ID: 4'}, {'i': 0, 'id': 'ID: 5'}, {'i': 0, 'id': 'ID: 6'}, {'i': 0, 'id': 'ID: 7'}, 
{'i': 0, 'id': 'ID: 8'}, {'i': 0, 'id': 'ID: 9'}]
>>> sorted(ids, key=lambda obj: obj['i'])
[{'i': 0, 'id': 'ID: 0'}, {'i': 0, 'id': 'ID: 1'}, {'i': 0, 'id': 'ID: 2'}, {'i': 0, 'id': 'ID: 3'},
{'i': 0, 'id': 'ID: 4'}, {'i': 0, 'id': 'ID: 5'}, {'i': 0, 'id': 'ID: 6'}, {'i': 0, 'id': 'ID: 7'},
{'i': 0, 'id': 'ID: 8'}, {'i': 0, 'id': 'ID: 9'}]

The order of the IDs is ascending (unaffected) in CPython whereas it is shuffled in Pycopy.

[GimmickNG]

After doing some digging, it seems this is a known issue:

https://github.com/pfalcon/pycopy/blob/d590892d235cdb318d0b830c1cedb6b81dad16d2/py/objlist.c#L343-L344

likely because of the use of quicksort instead of e.g. timsort: https://github.com/pfalcon/pycopy/blob/d590892d235cdb318d0b830c1cedb6b81dad16d2/py/objlist.c#L361-L363