Sort

Sort Up and Sort Down are monadic functions that order the major cells of an array in ascending or descending order. Traditionally these functions are performed using Grade in APL: for example the FinnAPL idiom library gives X[⍋X] and X[⍒X] to sort X ascending and descending, respectively. In several dialects or other array languages they are defined as primitives, but with widely varying glyphs: ∧∨ Extended Dyalog APL, Kap, and BQN, <> in dzaima/APL, and ≤≥ in Dyalog APL Vision, as well as ^ for ascending sort in K9 and Goal.

In Dyalog APL there are several recognized idioms for sorting: for ascending sorting, {⍵[⍋⍵]} and {⍵[⍋⍵;]} to sort rank 1 and 2 arrays specifically, and {(⊂⍋⍵)⌷⍵} to sort any rank (all idioms have the same performance; the rank-specific ones were defined first and are shorter). The same idioms are recognized for descending sorting, replacing ⍋ with ⍒.

Sorting with Grade is easiest using the Select (⊇) or From function, which for example allows the ascending sort function on any rank to be written as the train ⍋⊇⊢ in dzaima/APL. Using Reverse Compose ⍛ as implemented in Kap or Dyalog APL Vision, it can be written ⍋⍛⊇. In J, it's implemented as Sort By (/: for ascending) with Commute, /:~.

A dedicated sorting implementation can be substantially faster than grade and selection both because sorting is generally faster than grade (particularly for long vectors with small-width elements, where an index may take more storage space than an element) and because selection is cache-unfriendly. For small-range data, a moveless variant of counting sort is possible for sorting but not grading.^[1] Flags for sorted data, which can be used to optimize various operations on the flagged array, can more easily be set with a dedicated sorting function.^[2]

Documentation

Kap
BQN

References

↑ Marshall Lochbaum. Implementation of ordering functions. BQN implementation notes.
↑ Marshall Lochbaum. Sortedness flags in primitive implementation. BQN implementation notes.

APL built-ins [edit]
Primitives (Timeline)	Functions
Scalar
		Monadic	Conjugate ∙ Negate ∙ Signum ∙ Reciprocal ∙ Magnitude ∙ Exponential ∙ Natural Logarithm ∙ Floor ∙ Ceiling ∙ Factorial ∙ Not ∙ Pi Times ∙ Roll ∙ Type ∙ Imaginary ∙ Square Root
		Dyadic	Add ∙ Subtract ∙ Times ∙ Divide ∙ Residue ∙ Power ∙ Logarithm ∙ Minimum ∙ Maximum ∙ Binomial ∙ Comparison functions ∙ Boolean functions (And, Or, Nand, Nor) ∙ GCD ∙ LCM ∙ Circular ∙ Complex ∙ Root
Non-Scalar
		Structural	Shape ∙ Reshape ∙ Tally ∙ Depth ∙ Ravel ∙ Enlist ∙ Table ∙ Catenate ∙ Reverse ∙ Rotate ∙ Transpose ∙ Raze ∙ Mix ∙ Split ∙ Enclose ∙ Nest ∙ Cut (K) ∙ Pair ∙ Link ∙ Partitioned Enclose ∙ Partition
		Selection	First ∙ Pick ∙ Take ∙ Drop ∙ Unique ∙ Identity ∙ Stop ∙ Select ∙ Replicate ∙ Expand ∙ Set functions (Intersection ∙ Union ∙ Without) ∙ Bracket indexing ∙ Index ∙ Cartesian Product ∙ Sort
		Selector	Index generator ∙ Grade ∙ Index Of ∙ Interval Index ∙ Indices ∙ Deal ∙ Prefix and suffix vectors
		Computational	Match ∙ Not Match ∙ Membership ∙ Find ∙ Nub Sieve ∙ Encode ∙ Decode ∙ Matrix Inverse ∙ Matrix Divide ∙ Format ∙ Execute ∙ Materialise ∙ Range
Operators	Monadic	Each ∙ Commute ∙ Constant ∙ Replicate ∙ Expand ∙ Reduce ∙ Windowed Reduce ∙ Scan ∙ Outer Product ∙ Key ∙ I-Beam ∙ Spawn ∙ Function axis
Operators	Dyadic	Bind ∙ Compositions (Compose, Reverse Compose, Beside, Withe, Atop, Over) ∙ Inner Product ∙ Determinant ∙ Power ∙ At ∙ Under ∙ Rank ∙ Depth ∙ Variant ∙ Stencil ∙ Cut ∙ Direct definition (operator)
Quad names	Index origin ∙ Comparison tolerance ∙ Migration level ∙ Atomic vector

[1] Marshall Lochbaum. Implementation of ordering functions. BQN implementation notes.

[2] Marshall Lochbaum. Sortedness flags in primitive implementation. BQN implementation notes.

[1]

[2]

Sort

Documentation

References

Navigation menu

Search