# 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.

