>From 23f306510c4a00b539607b9e57486c7fb72f37bf Mon Sep 17 00:00:00 2001
From: Daniel Mendler <mail@daniel-mendler.de>
Date: Mon, 19 Apr 2021 13:17:23 +0200
Subject: [PATCH 5/6] completion-all-sorted-completions: Sort candidates in a
 single pass

* lisp/minibuffer.el (completion-all-sorted-completions): Decorate
each candidate with history position and length such that the list can
be sorted in a single pass.
---
 lisp/minibuffer.el | 23 ++++++++++++++---------
 1 file changed, 14 insertions(+), 9 deletions(-)

diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
index c7aec9665e..7146604ab4 100644
--- a/lisp/minibuffer.el
+++ b/lisp/minibuffer.el
@@ -1388,11 +1388,9 @@ completion-all-sorted-completions
            (sort-fun
             (setq all (funcall sort-fun all)))
            (t
-            ;; Prefer shorter completions, by default.
-            (setq all (sort all (lambda (c1 c2) (< (length c1) (length c2)))))
             (if (and (minibufferp) (not (eq minibuffer-history-variable t)))
-                ;; Prefer recently used completions and put the default, if
-                ;; it exists, on top.
+                ;; Sort first by history position and then by length.
+                ;; Put the default, if it exists, on top.
                 (let* ((hist (symbol-value minibuffer-history-variable))
                        (hash (make-hash-table :test #'equal :size (length hist)))
                        (index 0)
@@ -1426,19 +1424,26 @@ completion-all-sorted-completions
                         (unless (gethash c hash)
                           (puthash c index hash)))
                       (cl-incf index)))
-                  ;; Decorate elements with history position
+                  ;; Decorate each candidate with (index<<13) +
+                  ;; length. This way we sort first by index and then
+                  ;; by length. We assume that the candidates are
+                  ;; shorter than 2^13 characters and that the
+                  ;; history is shorter than 2^16 entries.
                   (let ((c all))
                     (while c
-                      (setcar c (cons (gethash (car c) hash
-                                               most-positive-fixnum)
-                                      (car c)))
+                      (setcar c (cons
+                                 (+ (lsh (gethash (car c) hash #xFFFF) 13)
+                                    (length (car c)))
+                                 (car c)))
                       (pop c)))
                   (setq all (sort all #'car-less-than-car))
                   ;; Drop decoration from the elements
                   (let ((c all))
                     (while c
                       (setcar c (cdar c))
-                      (pop c)))))))
+                      (pop c))))
+              ;; Sort only by length if no history is available.
+              (setq all (sort all (lambda (c1 c2) (< (length c1) (length c2))))))))
 
           ;; Cache the result.  This is not just for speed, but also so that
           ;; repeated calls to minibuffer-force-complete can cycle through
-- 
2.20.1