Ticket #0001152

Type	Bug	Status	built	Date	26-Jul-2009 20:47
Version	alpha 76	Category	Native	Submitted by	BrianH
Platform	All	Severity	minor	Priority	normal

Summary	SORT not stable (order not preserved)
Description	In this case, I am not referring to the stability of the function itself, but to whether the sorting algorithm is stable. When SORT finds two values that it considers equal, it reverses them in the results. Somewhere in SORT a < should be a <=, or something like that.
Example code	; Case-insensitive comparison - values are considered equal >> sort ["A" "a"] == ["a" "A"] ; should be ["A" "a"] >> sort ["a" "A"] == ["A" "a"] ; should be ["a" "A"] ; Case-sensitive comparison - values are considered different >> sort/case ["a" "A"] == ["A" "a"] ; good >> sort/case ["A" "a"] == ["A" "a"] ; good ; Verification using SAME? >> set [c d] sort reduce [a: "a" b: "a"] == ["a" "a"] >> same? c a == false ; should be true >> same? c b == true ; should be false >> same? d a == true ; should be false >> same? d b == false ; should be true

Summary

SORT not stable (order not preserved)

Description

In this case, I am not referring to the stability of the function itself, but to whether the sorting algorithm is stable. When SORT finds two values that it considers equal, it reverses them in the results. Somewhere in SORT a < should be a <=, or something like that.

Example code

; Case-insensitive comparison - values are considered equal
>> sort ["A" "a"]
== ["a" "A"]  ; should be ["A" "a"]
>> sort ["a" "A"]
== ["A" "a"]  ; should be ["a" "A"]

; Case-sensitive comparison - values are considered different
>> sort/case ["a" "A"]
== ["A" "a"]  ; good
>> sort/case ["A" "a"]
== ["A" "a"]  ; good

; Verification using SAME?
>> set [c d] sort reduce [a: "a" b: "a"]
== ["a" "a"]
>> same? c a
== false  ; should be true
>> same? c b
== true  ; should be false
>> same? d a
== true  ; should be false
>> same? d b
== false  ; should be true

Assigned to	n/a	Fixed in	r3 master	Last Update	18-Feb-2014 00:02

Comments
(0002967) Ladislav 10-Dec-2010 21:39	Using /compare we may come to a conclusion, that SORT probably would be stable, if using an appropriate comparison operator: ; this example behaves like the version not using /compare, being unstable >> sort/compare ["A" "a"] func [a b] [a < b] == ["a" "A"] ; this example behaves like the version not using /compare, being unstable >> sort/compare ["a" "A"] func [a b] [a < b] == ["A" "a"] ; this example is stable >> sort/compare ["A" "a"] func [a b] [a <= b] == ["A" "a"] ; this exaple is stable >> sort/compare ["a" "A"] func [a b] [a <= b] == ["a" "A"]
(0002968) abolka 10-Dec-2010 22:31	On A110 Linux, all test cases given in the example code succeed. Unfortunately, that result does not necessarily make this issue platform-specific. A quick trace shows that, at least on Linux, R3's SORT is using the C library's qsort() function. qsort() is, by definition, not stable. Quoting the C99 standard (7.22.5.2p4): "If two elements compare as equal, their order in the resulting sorted array is unspecified." This means (assuming that qsort() is used in Win32 R3 as well) that all effects we observed above are most likely purely coincidental, resulting from the underlying C library's implementation of qsort(). If we want SORT to be stable per default, there is a well-known hack for achieving that even with C's qsort(): "If you want the effect of a stable sort, you can get this result by writing the comparison function so that, lacking other reason distinguish between two elements, it compares them by their addresses. Note that doing this may make the sorting algorithm less efficient, so do it only if necessary." (Quoted from the glibc documentation: http://www.gnu.org/s/libc/manual/html_node/Array-Sort-Function.html) Alternatively, the implementation of SORT will have to forego qsort() and use a stable sort instead. Of course, maybe R3 is already employing that hack, and then this issue most likely really is a platform-specific bug. For reference: ; RT R3 A110 Linux >> sort/skip/compare [1 9 1 5 1 7] 2 1 == [1 9 1 5 1 7] ; RT R3 A110 Win32 >> sort/skip/compare [1 9 1 5 1 7] 2 1 == [1 7 1 9 1 5]
(0002969) abolka 11-Dec-2010 20:39	in the core-tests suite
(0002971) BrianH 12-Dec-2010 06:56	Gabriele pointed out in AltME that R2's SORT is stable, even on Windows, and testing bears that out.
(0004018) Ladislav 26-Sep-2013 19:43	Fixed by https://github.com/rebol/rebol/pull/152

Date	User	Field	Action	Change
18-Feb-2014 00:02	BrianH	Status	Modified	pending => built
18-Feb-2014 00:02	BrianH	Fixedin	Modified	=> r3 master
26-Sep-2013 19:56	Ladislav	Status	Modified	reviewed => pending
26-Sep-2013 19:43	Ladislav	Comment : 0004018	Added	-
12-Dec-2010 06:56	BrianH	Comment : 0002971	Added	-
11-Dec-2010 20:39	abolka	Comment : 0002969	Added	-
11-Dec-2010 13:27	abolka	Comment : 0002968	Modified	-
11-Dec-2010 13:14	abolka	Comment : 0002968	Modified	-
10-Dec-2010 22:52	abolka	Comment : 0002968	Modified	-
10-Dec-2010 22:43	abolka	Comment : 0002968	Modified	-
10-Dec-2010 22:32	abolka	Comment : 0002968	Modified	-
10-Dec-2010 22:32	abolka	Comment : 0002968	Modified	-
10-Dec-2010 22:31	abolka	Comment : 0002968	Modified	-
10-Dec-2010 22:31	abolka	Comment : 0002968	Modified	-
10-Dec-2010 22:31	abolka	Comment : 0002968	Added	-
10-Dec-2010 21:50	BrianH	Code	Modified	-
10-Dec-2010 21:39	Ladislav	Comment : 0002967	Added	-
3-Aug-2009 19:45	carl	Status	Modified	submitted => reviewed
3-Aug-2009 19:45	carl	Code	Modified	-
3-Aug-2009 19:45	carl	Summary	Modified	SORT not stable => SORT not stable (order not preserved)
26-Jul-2009 20:47	BrianH	Ticket	Added	-