(sort) semantics: stable ordering of elements compared '=' ?

[hartrock]

[2. Update 2014-01-02]: it has a stable ordering (see Lutz' reply).

[1. Update 2014-01-02]: added 'stable' to title (see replies below).



Example:

Code Select Expand


> (setq l '( ("0" 3) ("1" 3) ("2" 3) ("3" 3) ("4" 3)  ("foo" 2) ("bar" 4) ("foo" 1) ("bar" 5)  ("5" 3) ("6" 3) ("7" 3) ("8" 3) ("9" 3)))
(("0" 3) ("1" 3) ("2" 3) ("3" 3) ("4" 3) ("foo" 2) ("bar" 4) ("foo" 1) ("bar" 5) ("5" 3) ("6" 3) ("7" 3) ("8" 3) ("9" 3))
> (sort (copy l) (fn (x y) (<= (last x) (last y))))
(("foo" 1) ("foo" 2) ("0" 3) ("1" 3) ("2" 3) ("3" 3) ("4" 3) ("5" 3) ("6" 3) ("7" 3) ("8" 3) ("9" 3) ("bar" 4) ("bar" 5))
> (sort (copy l) (fn (x y) (< (last x) (last y))))
(("foo" 1) ("foo" 2) ("9" 3) ("8" 3) ("7" 3) ("6" 3) ("5" 3) ("4" 3) ("3" 3) ("2" 3) ("1" 3) ("0" 3) ("bar" 4) ("bar" 5))
> ;;
> (= (sort (copy l) (fn (x y) (< (last x) (last y)))) (reverse (sort (copy l) (fn (x y) (>= (last x) (last y))))))
true
> (= (sort (copy l) (fn (x y) (> (last x) (last y)))) (reverse (sort (copy l) (fn (x y) (<= (last x) (last y))))))
true


Observations:

Sorting with

- '<=' or '>=' does not change the order of elements compared '=';

- '<=' results into reversed elements of sorting with '>', and

- '>=' resutls into reversed elements of sorting with '<' .



Is this behavior guaranteed?

In the (sort) section of the manual there is no statement regarding the '=' case.

Sorting behavior of elements compared equal could be different without violating their sorting relation '<', '<=', '>' or '>=': in principle the ordering amongst elements compared '=' could be *arbitrary* after sorting.



Motivation:

I've started sorting a similar list with '<' and handled '=' elements specifically, because their order had changed compared with the original list (without being surprised about this effect). After that I've seen, that sorting with '<=' does exactly what I wanted (keeping original ordering of elements compared '='), without specific handling of the '=' case.

Question remains, if this can be exploited or is just an implementation incident (which may change in a later newLISP version).

[Astrobe]

This is a property named stability (https://en.wikipedia.org/wiki/Sorting_algorithm#Stability">https://en.wikipedia.org/wiki/Sorting_a ... #Stability">https://en.wikipedia.org/wiki/Sorting_algorithm#Stability), which depends on the sorting algorithm.

[hartrock]

This is a property named stability (https://en.wikipedia.org/wiki/Sorting_algorithm#Stability">https://en.wikipedia.org/wiki/Sorting_a ... #Stability">https://en.wikipedia.org/wiki/Sorting_algorithm#Stability), which depends on the sorting algorithm.

Thanks to the pointer: this is the point of my question.

I've updated the post title accordingly.



Condensed the question could be: is (sort) stable according the link above?

[Lutz]

Yes, it is a stable binary (two groups) merge-sort with almost linear O(n log2 n) performance preserving the order of adjacent elements which are equal when using <= or >=.





ps: this will be added to the manual