# Sorting routines This unit contains sorting routines as well as routines that take advantage of sorted data. ## A small word about bisect's effectiveness Linear search is pretty fast on small-ish datasets. Under 100 items, bisect is likely to be slower than linear search ("idx" and friends). So, hum, let's not get carried away with bisecting... ## API sort ( a u -- ) Sort u 32-bit elements at address a using the Quick Sort algorithm with Hoare's partitioning. sortpairs ( a u -- ) Sort u 64-bit elements at address a with the first 32-bit being the key and the second 32-bit being data to follow along as the key is moved around. bisect ( n a u -- idx f ) With "a u" being a range of sorted 32-bit elements, find the index at which number "n" belongs using a bisection algorithm. When "n" doesn't exist in the list and would belong at the very end of it, idx=u. idx never exceeds u. f=1 if the element at that index is equal to "n", f=0 otherwise. When the sorted list contains duplicates, the resulting "idx" can land on any of them. It's the fastest way to get a valid bisect result. bisectpairs ( n a u -- idx f ) Like "bisect", but with "a u" being pairs of two 32-bit elements, the first being the key, the second being the associated value. bisectleft ( n a u -- idx f ) Runs bisect and, if f=1, backtrack from found "idx" in order to ensure that the yielded idx is the leftmost one equal to "n". bisectpairsleft ( n a u -- idx f ) Like "bisectpairs" but with the "left" logic applied.