If index is a sorted index then entries are already sorted. So as an optimization you can skip sorting if index is sorted and comparator is null. You can add isSortedIndex() to IndexAwarePredicate interface