From 4495643b8377d8edf642f68ca5f39792dbf57494 Mon Sep 17 00:00:00 2001
From: Tyge Løvset <tylo@norceresearch.no>
Date: Thu, 12 Jan 2023 15:30:16 +0100
Subject: Made csort max recursion depth < log2(n).

---
 include/stc/algo/csort.h | 46 +++++++++++++++++++++++-----------------------
 misc/examples/sort.c     |  4 +++-
 2 files changed, 26 insertions(+), 24 deletions(-)

diff --git a/include/stc/algo/csort.h b/include/stc/algo/csort.h
index 110aa514..2cd7b548 100644
--- a/include/stc/algo/csort.h
+++ b/include/stc/algo/csort.h
@@ -74,32 +74,32 @@ static inline void c_PASTE(cisort_, i_tag)(i_val arr[], intptr_t lo, intptr_t hi
     }
 }
 
-static inline void c_PASTE(cqsort_, i_tag)(i_val arr[], intptr_t lo, intptr_t hi)
-{
-    intptr_t i = lo, j = hi;
-    i_val pivot = arr[lo + (hi - lo)*7/16];
+static inline void c_PASTE(cqsort_, i_tag)(i_val arr[], intptr_t lo, intptr_t hi) {
+    intptr_t i = lo, j;
+    while (lo < hi) {
+        i_val pivot = arr[lo + (hi - lo)*7/16];
+        j = hi;
 
-    while (i <= j) {
-        while (i_less((&arr[i]), (&pivot))) ++i;
-        while (i_less((&pivot), (&arr[j]))) --j;
-        if (i <= j) {
-            c_SWAP(i_val, arr+i, arr+j);
-            ++i; --j;
+        while (i <= j) {
+            while (i_less((&arr[i]), (&pivot))) ++i;
+            while (i_less((&pivot), (&arr[j]))) --j;
+            if (i <= j) {
+                c_SWAP(i_val, arr+i, arr+j);
+                ++i; --j;
+            }
         }
+        if (j - lo > hi - i) {
+            c_SWAP(intptr_t, &lo, &i);
+            c_SWAP(intptr_t, &hi, &j);
+        }
+
+        if (j - lo > 64) c_PASTE(cqsort_, i_tag)(arr, lo, j);
+        else if (j > lo) c_PASTE(cisort_, i_tag)(arr, lo, j);
+        lo = i;
     }
-    if (j - lo > hi - i) {
-        c_SWAP(intptr_t, &lo, &i);
-        c_SWAP(intptr_t, &hi, &j);
-    }
-    if (j - lo > 64) c_PASTE(cqsort_, i_tag)(arr, lo, j);
-    else if (j > lo) c_PASTE(cisort_, i_tag)(arr, lo, j);
-    if (hi - i > 64) c_PASTE(cqsort_, i_tag)(arr, i, hi);
-    else if (hi > i) c_PASTE(cisort_, i_tag)(arr, i, hi);
 }
 
 static inline void c_PASTE(csort_, i_tag)(i_val arr[], size_t n)
-{
-    if (n > 64) c_PASTE(cqsort_, i_tag)(arr, 0, (intptr_t)n - 1);
-    else        c_PASTE(cisort_, i_tag)(arr, 0, (intptr_t)n - 1);
-}
-#include <stc/priv/template.h>
\ No newline at end of file
+    { c_PASTE(cqsort_, i_tag)(arr, 0, (intptr_t)n - 1); }
+
+#include <stc/priv/template.h>
diff --git a/misc/examples/sort.c b/misc/examples/sort.c
index af74ff51..de94cede 100644
--- a/misc/examples/sort.c
+++ b/misc/examples/sort.c
@@ -42,6 +42,8 @@ int main(int argc, char *argv[]) {
     for (i = 0; i < 20; i++)
         printf(" " fmt_Elem, a[i]);
     puts("");
+    for (i = 1; i < size; i++)
+        if (a[i - 1] > a[i]) return -1;
 
     testsort(a, size, "sorted");
 
@@ -55,7 +57,7 @@ int main(int argc, char *argv[]) {
     a[size - 1] = 0;
     testsort(a, size, "rotated");
 
-    for (i = 0; i < size; i++) a[i] = i % (size / 2);
+    for (i = 0; i < size; i++) a[i] = i % (size / 8);
     testsort(a, size, "repeated");
 
     free(a);
-- 
cgit v1.2.3