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.

1 files changed, 15 insertions, 0 deletions

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))