Какой использовать алгоритм сортировки, если требуется сложность не более O(n) и максимальная производительность?

> log тут по основанию 2

Это неверное уточнение. В O-нотации логарифм может быть с любым основанием, т.к. два логарифма с разными основаниями отличаются друг от друга на мультипликативную константу.

Алгоритм для быстрой проверки соответствия строки шаблонам?

Обнаружил, в чём была проблема. Она была не в самом дереве префиксов. Узким местом было чтение данных. Класс Scanner, который я использовал для этого, работает слишком медленно из-за большого количества проверок на соответствие типов и т.п. (хоть я и читал лишь строки функцией nextLine() и, по идее, никакие проверки не были нужны). Стоило заменить Scanner на BufferedReader и всё заработало за приемлемое время.

Алгоритм для быстрой проверки соответствия строки шаблонам?

SeptiM, попробовал использовать массив. К сожалению, это не помогло. Значит, проблема, скорее всего в запросах matches().

Алгоритм для быстрой проверки соответствия строки шаблонам?

Спасибо за ответ. Я попробовал реализовать через дерево префиксов. Правда, несколько иначе, чем вы описали. Вроде бы, код работает корректно, но недостаточно быстро. Не могли бы вы посмотреть, может, я что-то написал неверно или неэффективно? pastebin.com/DKZzhvXA