1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
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);
}
}
|
