Share your thoughts in the 2024 State of Clojure Survey!

Welcome! Please see the About page for a little more info on how this works.

0 votes
in ClojureScript by

Clojure sort and sort-by both promise "Guaranteed to be stable: equal elements will not be reordered."

The current implementations of sort and sort-by in ClojureScript are from

9ee4dbf63d3968b70f29708aa03aace98cdcb624 Author: Stuart Halloway <stu@thinkrelevance.com> AuthorDate: Thu Jul 14 12:18:34 2011 -0500

`
(defn sort
"Returns a sorted sequence of the items in coll. Comp can be
boolean-valued comparison function, or a -/0/+ valued comparator.
Comp defaults to compare."
([coll]
(sort compare coll))
([comp coll]
(if (seq coll)

 (let [a (to-array coll)]
   ;; matching Clojure's stable sort, though docs don't promise it
   (garray/stableSort a (fn->comparator comp))
   (seq a))
 ())))

(defn sort-by
"Returns a sorted sequence of the items in coll, where the sort
order is determined by comparing (keyfn item). Comp can be
boolean-valued comparison function, or a -/0/+ valued comparator.
Comp defaults to compare."
([keyfn coll]
(sort-by keyfn compare coll))
([keyfn comp coll]

 (sort (fn [x y] ((fn->comparator comp) (keyfn x) (keyfn y))) coll)))

`

Since this implementation has apparently called google's stableSort for the last 8 years perhaps the docstring could be amended to reflect this.

For reference, the google closure array documentation: (link: https://google.github.io/closure-library/api/goog.array.html):

Note that stableSort's docstring actually doesn't mention stability but the sort function contains "This sort is not guaranteed to be stable."

5 Answers

0 votes
by

Comment made by: seancorfield

(from a discussion on Slack, I offered this opinion which someone suggested I should add to this ticket)

I think it would be good to explicitly state either:

Guaranteed to be stable: equal elements will not be reordered.

or:

Not guaranteed to be stable.

That way developers will know that either they can depend on stability or they should not depend on it (even tho' the current implementation happens to be stable).

0 votes
by

Comment made by: pbwolf

Clojure's sort docstring says, "Guaranteed to be stable: equal elements will not be reordered." Earlier, it had been stable but not documented as such. See https://dev.clojure.org/jira/browse/CLJ-1414

I hope CLJS will (a) be stable in the same way and (b) match Clojure's documentation of stability.

0 votes
by

Comment made by: saurabh

I would like to to work on this issue, if it is still open

0 votes
by

Comment made by: dnolen

Go for it, have you submitted your CA?

0 votes
by
Reference: https://clojure.atlassian.net/browse/CLJS-3035 (reported by dpsutton)
...