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:

pycopy/py/objlist.c

Lines 343 to 344 in d590892

	// TODO Python defines sort to be stable but ours is not
	mp_obj_t mp_obj_list_sort(size_t n_args, const mp_obj_t *pos_args, mp_map_t *kw_args) {

likely because of the use of quicksort instead of e.g. timsort:

pycopy/py/objlist.c

Lines 361 to 363 in d590892

	mp_quicksort(self->items, self->items + self->len - 1,
	args.key.u_obj == mp_const_none ? MP_OBJ_NULL : args.key.u_obj,
	args.reverse.u_bool ? mp_const_false : mp_const_true);