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 +++++++++++++++++++++++-----------------------
 1 file changed, 23 insertions(+), 23 deletions(-)

(limited to 'include/stc/algo/csort.h')

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>
-- 
cgit v1.2.3