1 files changed, 125 insertions, 0 deletions
diff --git a/vere/pkg/noun/jets/b/sort.c b/vere/pkg/noun/jets/b/sort.c
new file mode 100644
index 0000000..ea5507c
--- /dev/null
+++ b/vere/pkg/noun/jets/b/sort.c
@@ -0,0 +1,125 @@
+/// @file
+
+#include "jets/q.h"
+#include "jets/w.h"
+
+#include "noun.h"
+
+
+static_assert( (UINT32_MAX > u3a_cells),
+               "length precision" );
+
+static_assert(
+  (UINT32_MAX < (SIZE_MAX / (2 * sizeof(u3_noun)))),
+  "len_w * sizeof u3_noun overflow"
+);
+
+static void
+_merge_sort(u3_noun* restrict arr_u,
+  u3_noun* restrict tmp_u,
+  c3_w lef_w,
+  c3_w rit_w,
+  u3j_site* sit_u)
+{
+  if ( lef_w >= rit_w ) return;
+  c3_w mid_w =  (lef_w + rit_w) / 2;
+  if (mid_w < lef_w)
+  {
+    //  addition wrapped around
+    //
+    u3m_bail(c3__fail);
+  }
+  _merge_sort(arr_u, tmp_u, lef_w, mid_w, sit_u);
+  _merge_sort(arr_u, tmp_u, mid_w + 1, rit_w, sit_u);
+
+  c3_w i_w = lef_w, j_w = mid_w + 1, k_w = lef_w;
+  while (i_w <= mid_w && j_w <= rit_w)
+  {
+    //  reversed comparison to mimick order reversal of pivot
+    //  and compared element in Hoon
+    //
+    u3_noun sam = u3nc(u3k(arr_u[j_w]), u3k(arr_u[i_w]));
+    c3_o hoz_o = u3x_loob(u3j_gate_slam(sit_u, sam));
+    if ( c3n == hoz_o )
+      tmp_u[k_w++] = arr_u[i_w++];
+    else
+      tmp_u[k_w++] = arr_u[j_w++];
+  }
+
+  while (i_w <= mid_w) tmp_u[k_w++] = arr_u[i_w++];
+  while (j_w <= rit_w) tmp_u[k_w++] = arr_u[j_w++];
+
+  for (i_w = lef_w; i_w <= rit_w; i_w++)
+  {
+    arr_u[i_w] = tmp_u[i_w];
+  }
+}
+
+//  RETAINS list, transfers product
+//
+static u3_noun
+_sort(u3j_site* sit_u, u3_noun list)
+{
+  if (u3_nul == list) return u3_nul;
+
+  c3_w len_w = 1;
+  {
+    u3_noun t = u3t(list);
+    while (u3_nul != t)
+    {
+      ++len_w; t = u3t(t);
+    }
+  }
+
+  if (1 == len_w) return u3k(list);
+  u3_noun* arr_u = u3a_malloc(sizeof(u3_noun) * len_w * 2);
+  u3_noun* tmp_u = arr_u + len_w;
+  for (c3_w i_w = 0; i_w < len_w; i_w++)
+  {
+    //  inlined u3r_cell without any checks
+    //  since the list was already validated and measured
+    //
+    u3a_cell* cel_u = u3a_to_ptr(list);
+    arr_u[i_w] = u3k(cel_u->hed);
+    list = cel_u->tel;
+  }
+
+  _merge_sort(arr_u, tmp_u, 0, len_w - 1, sit_u);
+
+  u3_noun pro = u3_nul;
+  for (c3_w i_w = len_w; i_w--;)
+  {
+    pro = u3nc(arr_u[i_w], pro);
+  }
+  
+  u3a_free(arr_u);
+
+  return pro;
+}
+
+u3_noun
+u3qb_sort(u3_noun a,
+          u3_noun b)
+{
+  u3_noun  pro;
+  u3j_site sit_u;
+  u3j_gate_prep(&sit_u, u3k(b));
+  pro = _sort(&sit_u, a);
+  u3j_gate_lose(&sit_u);
+  return pro;
+}
+
+u3_noun
+u3wb_sort(u3_noun cor)
+{
+  u3_noun a, b;
+
+  if ( c3n == u3r_mean(cor, u3x_sam_2, &a, u3x_sam_3, &b, 0) )
+  {
+    return u3m_bail(c3__exit);
+  }
+  else
+  {
+    return u3qb_sort(a, b);
+  }
+}