FWIW, I tried caching the results of isUnique in a record.  Once we know a record is unique within a particular index segment, it will remain unique for the rest of the recursive steps that contain the record, because each step is splitting the index in half (or even smaller).

The caching worked by shifting the element position up 1 bit and OR'ing in 1 as soon as we found the element was unique.  The start of the method then became:

  if ((rec & 1) != 0)
   return true;

This turned out to be slower on every system I tried it on, but I suspect its artificial due to the type of Sequence being used by the performance test.  equals() on that char[] based sequence used by the test is insanely fast.  equals() on a larger line input like RawText uses is a lot slower.  We should revisit this caching concept by testing on a more common input.