From 9d62dcc6c87a98faad5a494bbd7d472d1e648d47 Mon Sep 17 00:00:00 2001
From: Kaz Kylheku <kaz@kylheku.com>
Date: Mon, 1 May 2023 16:42:10 -0700
Subject: sort: replace Lomuto partitioning with Hoare

I'm seeing numbers aobut the same performance on a
sorted vector of integers, and 21% faster on vector of N
random integers in the range [0, N).
Also, this original algorithm handles well the case
of an array consisting of a repeated value.
The code we are replacing degrates to quadratic time.

* lib.c (med_of_three, middle_pivot): We don't use
the return value, so don't calculate and return one.
(quicksort): Revise to Hoare: scanning from both ends
of the array, exchanging elements.

* tests/010/sort.tl: New file. We test sort with
lists and vectors from length zero to eight, all
permutations.
---
 lib.c             | 65 ++++++++++++++++++++++++++++++-------------------------
 tests/010/sort.tl | 15 +++++++++++++
 2 files changed, 50 insertions(+), 30 deletions(-)
 create mode 100644 tests/010/sort.tl

diff --git a/lib.c b/lib.c
index 417109dd..fdc2d382 100644
--- a/lib.c
+++ b/lib.c
@@ -10791,7 +10791,7 @@ static void swap(val vec, val i, val j)
   }
 }
 
-static cnum med_of_three(val vec, val lessfun, val keyfun, cnum from, cnum to,
+static void med_of_three(val vec, val lessfun, val keyfun, cnum from, cnum to,
                          val *pkval)
 {
   cnum mid = from + (to - from) / 2;
@@ -10803,62 +10803,67 @@ static cnum med_of_three(val vec, val lessfun, val keyfun, cnum from, cnum to,
   val tkval = funcall1(keyfun, tval);
 
   if (funcall2(lessfun, fkval, mkval)) {
-    if (funcall2(lessfun, mkval, tval)) {
+    if (funcall2(lessfun, mkval, tval))
       *pkval = mkval;
-      return mid;
-    } else if (funcall2(lessfun, fkval, tkval)) {
+    else if (funcall2(lessfun, fkval, tkval))
       *pkval = tkval;
-      return to - 1;
-    } else {
+    else
       *pkval = fkval;
-      return from;
-    }
   } else {
-    if (funcall2(lessfun, fkval, tval)) {
+    if (funcall2(lessfun, fkval, tval))
       *pkval = fkval;
-      return from;
-    } else if (funcall2(lessfun, mkval, tkval)) {
+    else if (funcall2(lessfun, mkval, tkval))
       *pkval = tkval;
-      return to - 1;
-    } else {
+    else
       *pkval = mkval;
-      return mid;
-    }
   }
 }
 
-static cnum middle_pivot(val vec, val keyfun, cnum from, cnum to,
+static void middle_pivot(val vec, val keyfun, cnum from, cnum to,
                          val *pkval)
 {
   cnum pivot = from + (to - from) / 2;
   val pval = ref(vec, num_fast(pivot));
   *pkval = funcall1(keyfun, pval);
-  return pivot;
 }
 
 static void quicksort(val vec, val lessfun, val keyfun, cnum from, cnum to)
 {
   while (to - from >= 2) {
+    cnum i = from - 1;
+    cnum j = to;
     val pkval;
-    cnum i, j;
-    cnum pivot = if3(to - from > 15,
-                     med_of_three(vec, lessfun, keyfun, from, to, &pkval),
-                     middle_pivot(vec, keyfun, from, to, &pkval));
 
-    swap(vec, num_fast(pivot), num_fast(to - 1));
+    if (to - from > 15)
+      med_of_three(vec, lessfun, keyfun, from, to, &pkval);
+    else
+      middle_pivot(vec, keyfun, from, to, &pkval);
+
+    for (;;) {
+      do {
+        i++;
+      } while (funcall2(lessfun,
+                        funcall1(keyfun, ref(vec, num_fast(i))),
+                        pkval));
 
-    for (j = from, i = from; i < to - 1; i++)
-      if (funcall2(lessfun, funcall1(keyfun, ref(vec, num_fast(i))), pkval))
-        swap(vec, num_fast(i), num_fast(j++));
+      do {
+        j--;
+      } while (i < j && funcall2(lessfun,
+                                 pkval,
+                                 funcall1(keyfun, ref(vec, num_fast(j)))));
 
-    swap(vec, num_fast(j), num_fast(to - 1));
+      if (i >= j)
+        break;
+
+      swap(vec, num_fast(i), num_fast(j));
+    }
 
     if (j - from > to - j) {
-      quicksort(vec, lessfun, keyfun, j + 1, to);
-      to = j;
+      quicksort(vec, lessfun, keyfun, i, to);
+      to = i;
     } else {
-      quicksort(vec, lessfun, keyfun, from, j);
-      from = j + 1;
+      quicksort(vec, lessfun, keyfun, from, i);
+      from = i;
     }
   }
 }
diff --git a/tests/010/sort.tl b/tests/010/sort.tl
new file mode 100644
index 00000000..40ba8519
--- /dev/null
+++ b/tests/010/sort.tl
@@ -0,0 +1,15 @@
+(load "../common")
+
+(test (sort ()) nil)
+
+(let* ((list (conses '(1 2 3 4 5 6 7 8)))
+       (sp (uniq [mapcar sort (perm list (len list))])))
+  (mvtest (len sp) 1
+          (car sp) list))
+
+(test (sort #()) #())
+
+(let* ((vec (conses #(1 2 3 4 5 6 7 8)))
+       (sp (uniq [mapcar sort (perm vec (len vec))])))
+  (mvtest (len sp) 1
+          (car sp) vec))
-- 
cgit v1.2.3