Skip to content

sort/sort_by order equal elements by the platform qsort: unstable on macOS, stable on glibc (fixed on phase2 f7191b7e) #1982

Closed

Description

@InauguralPhysicist

sort and sort_by call the platform qsort. glibc's is in practice a stable merge sort; macOS's qsort is not stable. So equal elements, or equal sort_by keys, can come out in a different order on macOS than on Linux, with no error. That is a silent cross-platform divergence: a program, and a recorded tape replayed on another OS, can disagree.

How it surfaced: phase2-numbers R1.7. N6 prints an integral float as 3.0 and an int as 3, so an int/float tie that sorted "equal" became visible in text, and tests/test_boxed_int_containers.eigs ("sort exact order") failed on the macOS lane only (full lane run 40271709027). On main the same instability is reachable through sort_by with equal keys on distinguishable elements.

Fixed on phase2: in the R1.7 fix-forward (commit f7191b7e, on phase2-numbers since f406359), sort and sort_by are STABLE on every platform: a merge sort with an index tie-break, independent of libc, the freestanding eigs_qsort path included. BUILTINS.md documents it. A forced-quicksort plant reds the test.

Done when

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    area:stdlibSubsystem: stdlibkind:silent-wrongWrong answer with rc 0 -- the worst class; outranks every other kind

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions