CBQN has flags for arrays to indicate that the cells are ordered (as if sorted): one for ascending ordering and one for descending. Both flags together mean all cells are the same. These flags can be set in many cases, and allow for faster operation in many primitives, including asymptotic improvements. They're particularly important for Bins (โโ
) to avoid checking that a large ๐จ
is sorted in order to search a much smaller ๐ฉ
.
Trivial cases of arithmetic imply flags: for the identity, flags of a
are maintained, and constant results can have both flags set.
Many primitives are monotonic in each argument. For example, if aโคb
, then (a<k)โฅ(b<k)
, that is, <
is monotonically descending in ๐จ
. In the table below, + indicates an ascending argument, which corresponds to maintained order, while  indicates a descending argument and swapped order. The result inherits any flags shared by ๐จ
and ๐ฉ
(so, a bitwise and) after swapping flags for any descending arguments. Since it's reused, a scalar argument is effectively constant and should count as having both flags set. Table โ
counts as having a constant right argument.
Prim  Bool  ๐จ 
๐ฉ 

+โโ 
โจโงร 
+  + 
>โฅยฌ 
+    
<โค 
  + 
Multiplication by a constant factor with รโงรท
, such as kรv
or vรทk
, maintains the ordering of v
if k
is positive, reverses it if negative, and gives a constant result if zero and v
is finite.
The following scans F`
have ordered results. Since F`โพโฝ
applies โฝ
to the result of F`
, it gives the opposite ordering.
Prim  Bool  Order 

โ 
รโง 
Ascending 
โ 
+โจ 
Descending 
Other primitives have the effects listed below.
Prim  Monadic  Dyadic 

โ 
Sorted up  Same as ๐ฉ 
/ 
Sorted up  Same as ๐ฉ 
โ 
Sorted up  Same as ๐ฉ if no fills 
โ 
Same as ๐ฉ 
Same as ๐ฉ 
โฝ 
Swaps flags  
โฅ 
sโฅatom is constant 

โ 
Same as ๐จ if ๐ฉ up, swapped if ๐ฉ down 

โ 
Up if ๐ฉ sorted 

โท 
Same as ๐ฉ 

โ 
Elements sorted up  Elements same as ๐ฉ 
โพยซยป 
Checkable if ๐จ and ๐ฉ both ordered 
As โพยซยป
are fast operations and require a check that can be relatively expensive on short arguments, it's not clear whether they should try to maintain sortedness flags.
Ordering functions โงโจโโ
can use flags in obvious ways: presorted arguments make Sort and Grade trivial, and Bins should check for a sortedness flag before attempting to verify that ๐จ
is sorted.
Both Bins โโ
and Searches โโโโท
can apply adaptive galloping methods if both arguments are sorted. There's extensive research on these techniques but I don't have much experience with them.
The minimum and maximum of an ordered list are its first and last cells (reversed if sorted down). This is useful for primitives that perform range checking, as well as folds and scans with โ
or โ
. In particular, the scan either returns ๐ฉ
or acts as โฃ`
.
Sorted arguments can be split into runs with binary searches. If the range is much smaller than the length then the runs must be long on average. Then operations such as /โผ
or +ยด
where a run can be processed in constant time can process runs quickly. For example, +ยด
on a sorteddescending boolean list is simply the index of the first 0
as found by a binary search. Other cases include ๐ฉ
for monadic /
, ๐จ
for /
and โ
, scans with +
or boolean โ =
, and Match (โกโข
) if both arguments are sorted in the same direction.
Smallrange selection can be performed with inregister shuffles. For โ
with sorted ๐จ
, an adaptive technique is to operate on ๐จ
one vector register at a time, checking the range with the first and last element. Then either a shuffle or gather can be used as appropriate, or even a broadcast if the first and last index are equal.