luciakalf opened a new pull request, #779: URL: https://github.com/apache/datasketches-java/pull/779
Fixes #739 ## What `Sort.stableSort` (used by `TDigestDouble.merge`) ordered centroids only by value. Centroids with equal values but different weights ended up in an order that depended on the input order and on the random pivot, so the same input could produce different merged sketches. The sort now orders by value and, for equal values, by ascending weight, as agreed in the issue. It is pure Java with no new dependencies. ## Changes - `Sort.java`: the quicksort and insertion sort compare (value, weight) pairs. The partition is a standard three-way partition around the pivot pair. Pairs equal to the pivot are identical, so the previous pivot-index handling is no longer needed. - `SortTest.java`: new tests for the example from the issue, independence from input order (shuffled input), agreement with a reference sort for sizes around the insertion-sort threshold (63/64/65), and sorting only the requested prefix. Note: when `reverseMerge_` is set, the sorted arrays are reversed, so equal values are then processed in descending weight. This is still deterministic. ## Testing - `mvn test` on JDK 25: 2294 tests, 0 failures (including `TDigestCrossLanguageTest` and `TDigestDoubleSerializationTest`). - 3 of the 4 new tests fail on the previous implementation and pass with this change. - Building a `TDigestDouble` from the same 200,000 values with many duplicates 8 times produced 8 different serialized sketches before the change and 1 after. Quantiles are essentially unchanged. ## Performance Simple timing of `Sort.stableSort` (median, not JMH): - distinct values: no measurable difference (n=500: ~27 us) - many duplicates (20 distinct values): about 2x slower (n=10,000: 0.50 ms -> 1.05 ms), because equal values are now actually ordered by weight. At typical merge sizes this is a few microseconds. This change was developed with the help of Claude (Anthropic), as suggested in the issue. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
