heapq.nsmallest violates sorted equivalence for ordering-equivalent objects with identity equality

[augusto-rehfeldt]

Bug report

Bug description:

Documented behaviour: The nsmallest docstring states: "Equivalent to: sorted(iterable, key=key)[:n]". Python's sorting documentation guarantees that sorts are stable.

Expected: ['e', 'a', 'b', 'c'], with exactly those object identities in that order

Actual: ['e', 'a', 'd', 'b']

import heapq

class Item:
    def __init__(self, name, priority):
        self.name, self.priority = name, priority
    def __lt__(self, other):
        return self.priority < other.priority

data = [('a', 1), ('b', 1), ('c', 1), ('d', 1), ('e', 0)]
xs = [Item(*pair) for pair in data]
n = 4

if not (type(n) is int and 0 < n < len(xs)
        and all(type(x.priority) is int for x in xs)
        and all((x == y) == (x is y)
                and (x < y) == (x.priority < y.priority)
                for x in xs for y in xs)):
    print("REFUTATION REJECTED: invalid input")
else:
    actual = heapq.nsmallest(n, xs)
    expected = sorted(xs)[:n]
    if len(actual) != len(expected) or any(
            a is not e for a, e in zip(actual, expected)):
        print("REFUTATION CONFIRMED:",
              {'n': n, 'xs': data},
              "actual:", [x.name for x in actual],
              "expected:", [x.name for x in expected])
    else:
        print("REFUTATION REJECTED: actual matches sorted(xs)[:n] by identity and order")

Output on Python 3.14.6 (Windows-11-10.0.26220-SP0), standard library heapq:

REFUTATION CONFIRMED: {'n': 4, 'xs': [('a', 1), ('b', 1), ('c', 1), ('d', 1), ('e', 0)]} actual: ['e', 'a', 'd', 'b'] expected: ['e', 'a', 'b', 'c']

This report was found and written by an automated property-testing tool I run (bugforge). The reproducer above was executed and its output is pasted unedited; no person reviewed the report before it was filed. The search script is in https://github.com/augusto-rehfeldt/bugforge-results/tree/main/heapq-20261003-061723-c4

CPython versions tested on:

3.14

Operating systems tested on:

Windows

[ZeroIntensity]

See #158748 (comment).