[elpa] externals/compat b9bf90e71c 2/5: compat-25: Optimize sort, improve test

[ELPA Syncer]

branch: externals/compat
commit b9bf90e71c32ac3250f9a6a37eb809d836beb159
Author: Daniel Mendler <mail@daniel-mendler.de>
Commit: Daniel Mendler <mail@daniel-mendler.de>

    compat-25: Optimize sort, improve test
    
    O(n²) -> O(nlogn)
---
 compat-25.el    | 11 +++++++----
 compat-tests.el | 13 +++++++++++--
 2 files changed, 18 insertions(+), 6 deletions(-)

diff --git a/compat-25.el b/compat-25.el
index 157fc31048..ef0c78b398 100644
--- a/compat-25.el
+++ b/compat-25.el
@@ -49,10 +49,13 @@ usage: (bool-vector &rest OBJECTS)"
    ((listp seq)
     (sort seq predicate))
    ((vectorp seq)
-    (let ((cseq (sort (append seq nil) predicate)))
-      (dotimes (i (length cseq))
-        (setf (aref seq i) (nth i cseq)))
-      (apply #'vector cseq)))
+    (let ((list (sort (append seq nil) predicate))
+          (p list)
+          (i 0))
+      (while p
+        (aset seq i (car p))
+        (setq i (1+ i) p (cdr p)))
+      (apply #'vector list)))
    ((signal 'wrong-type-argument 'list-or-vector-p))))
 
 ;;;; Defined in editfns.c
diff --git a/compat-tests.el b/compat-tests.el
index 3156b87ba3..69684582db 100644
--- a/compat-tests.el
+++ b/compat-tests.el
@@ -1060,10 +1060,19 @@
   (should-equal '(1 2 3 4) (flatten-tree '(((1 nil)) 2 (((3 nil nil) 4))))))
 
 (ert-deftest sort ()
+  (should-equal (list 1 2 3) (sort (list 1 2 3) #'<))
+  (should-equal (list 1 2 3) (sort (list 1 3 2) #'<))
+  (should-equal (list 1 2 3) (sort (list 3 2 1) #'<))
   (should-equal (list 1 2 3) (compat-call sort (list 1 2 3) #'<))
+  (should-equal (list 1 2 3) (compat-call sort (list 1 3 2) #'<))
   (should-equal (list 1 2 3) (compat-call sort (list 3 2 1) #'<))
-  (should-equal '[1 2 3] (compat-call sort '[1 2 3] #'<))
-  (should-equal '[1 2 3] (compat-call sort '[3 2 1] #'<)))
+  (should-equal [1 2 3] (compat-call sort [1 2 3] #'<))
+  (should-equal [1 2 3] (compat-call sort [1 3 2] #'<))
+  (should-equal [1 2 3] (compat-call sort [3 2 1] #'<))
+  ;; Test side effect
+  (let ((vec [4 5 8 3 1 2 3 2 3 4]))
+    (compat-call sort vec #'>)
+    (should-equal vec [8 5 4 4 3 3 3 2 2 1])))
 
 (ert-deftest replace-string-in-region ()
   (with-temp-buffer