From 65eef4fade5eb426dae01d480f383b8a30b23071 Mon Sep 17 00:00:00 2001 From: Marshall Lochbaum Date: Wed, 11 Aug 2021 14:06:02 -0400 Subject: Change "BQN / main" in header to "(github) / BQN" --- docs/implementation/primitive/sort.html | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'docs/implementation/primitive/sort.html') diff --git a/docs/implementation/primitive/sort.html b/docs/implementation/primitive/sort.html index 86c36738..2a417770 100644 --- a/docs/implementation/primitive/sort.html +++ b/docs/implementation/primitive/sort.html @@ -3,7 +3,7 @@ BQN: Implementation of ordering functions - +

Implementation of ordering functions

The ordering functions are Sort (∧∨), Grade (⍋⍒), and Bins (⍋⍒). Although these are well-studied—particularly sorting, and then binary search or "predecessor search"—there are many recent developments, as well as techniques that I have not found in the literature. The three functions are closely related but have important differences in what algorithms are viable. Sorting is a remarkably deep problem with different algorithms able to do a wide range of amazing things, and sophisticated ways to combine those. It is by no means solved. In comparison, Bins is pretty tame.

There's a large divide between ordering compound data and simple data. For compound data comparisons are expensive, and the best algorithm will generally be the one that uses the fewest comparisons. For simple data they fall somewhere between cheap and extremely cheap, and fancy branchless and vectorized algorithms are the best.

-- cgit v1.2.3