[SR-1990] Sort has incorrect result on small collections with NaN values #44599

natecook1000 · 2016-07-05T17:20:07Z


Previous ID	SR-1990
Radar	None
Original Reporter	@natecook1000
Type	Bug

Environment

swift/master

Additional Detail from JIRA


Votes	0
Component/s	Standard Library
Labels	Bug
Assignee	None
Priority	Medium

md5: 1e24ceab6b5543ae4fa3b7ac98bf9564

relates to:

SR-1011 Fix Swift's min and max

Issue Description:

When sorting an array of floating-point values, an NaN value will "reset" sorting for a collection with fewer than 20 elements.

(swift) var a = Array(stride(from: 20.0, through: 0.0, by: -1.0))
(swift) a[5] = .nan
// a : Array<Double> = [20.0, 19.0, 18.0, 17.0, 16.0, nan, 14.0, 13.0, 12.0, 11.0, 10.0, 9.0, 8.0, 7.0, 6.0, 5.0, 4.0, 3.0, 2.0, 1.0, 0.0]

(swift) a.prefix(19).sorted()
// r1 : [Double] = [16.0, 17.0, 18.0, 19.0, 20.0, nan, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 12.0, 13.0, 14.0]
(swift) a.prefix(20).sorted()
// r2 : [Double] = [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 12.0, 13.0, 14.0, 16.0, 17.0, 18.0, 19.0, 20.0, nan]

sort() opts into an insertion sort at that size, which uses !(a[i] < a[i - 1]) to test whether an element at i is sorted correctly. Since (NaN < x) is false for all x, that's always true.

swift-ci transferred this issue from apple/swift-issues Apr 25, 2022

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

[SR-1990] Sort has incorrect result on small collections with NaN values #44599

[SR-1990] Sort has incorrect result on small collections with NaN values #44599

natecook1000 commented Jul 5, 2016

[SR-1990] Sort has incorrect result on small collections with NaN values #44599

[SR-1990] Sort has incorrect result on small collections with NaN values #44599

Comments

natecook1000 commented Jul 5, 2016