sorted is not stable

[LukeSavefrogs]

⚠️ Problem

Python sorting algorithm is guaranteed to be stable, while the polyfill is NOT stable.

🧪 Tests

The purpose of this test is to sort a list of dictionaries first by the result key (ascending order), then by the duration key (descending order).

✅ Python (3.9)

This works as expected, since the returned output is ordered by result (first the entries with 0) then by duration (biggest to smallest).

Code:

import json

obj = [{'duration': 0, 'result': 0}, {'duration': 15, 'result': 1}, {'duration': 7, 'result': 0}, {'duration': 22, 'result': 1}, {'duration': 10, 'result': 0}, {'duration': 18, 'result': 1}, {'duration': 5, 'result': 0}, {'duration': 12, 'result': 1}, {'duration': 20, 'result': 0}, {'duration': 8, 'result': 1}]

print(json.dumps(sorted(sorted(obj, key=lambda x: int(x["duration"]), reverse=True), key=lambda x: x["result"]), indent=4))

Output:

[
    {
        "duration": 20,
        "result": 0
    },
    {
        "duration": 10,
        "result": 0
    },
    {
        "duration": 7,
        "result": 0
    },
    {
        "duration": 5,
        "result": 0
    },
    {
        "duration": 0,
        "result": 0
    },
    {
        "duration": 22,
        "result": 1
    },
    {
        "duration": 18,
        "result": 1
    },
    {
        "duration": 15,
        "result": 1
    },
    {
        "duration": 12,
        "result": 1
    },
    {
        "duration": 8,
        "result": 1
    }
]

❌ Jython 2.1

This test fails, since the returned output is sorted only by result, while the duration key is not even in the same order as the input list.

Code:

import polyfills.json as json
from polyfills.stdlib.functions import sorted

obj = [{'duration': 0, 'result': 0}, {'duration': 15, 'result': 1}, {'duration': 7, 'result': 0}, {'duration': 22, 'result': 1}, {'duration': 10, 'result': 0}, {'duration': 18, 'result': 1}, {'duration': 5, 'result': 0}, {'duration': 12, 'result': 1}, {'duration': 20, 'result': 0}, {'duration': 8, 'result': 1}]

print(json.dumps(sorted(sorted(obj, key=lambda x: int(x["duration"]), reverse=True), key=lambda x: x["result"]), indent=4))

Output:

[
    {
        "result": 0,
        "duration": 10
    },
    {
        "result": 0,
        "duration": 20
    },
    {
        "result": 0,
        "duration": 5
    },
    {
        "result": 0,
        "duration": 7
    },
    {
        "result": 0,
        "duration": 0
    },
    {
        "result": 1,
        "duration": 8
    },
    {
        "result": 1,
        "duration": 22
    },
    {
        "result": 1,
        "duration": 12
    },
    {
        "result": 1,
        "duration": 15
    },
    {
        "result": 1,
        "duration": 18
    }
]

[LukeSavefrogs]

Ordering algorithms

Prior to v2.3 Python seemed to use an adapted version of quicksort (unstable, most probably samplesort), from v2.3 to v3.10 it used timsort, while from v3.10 on it uses powersort