Скорость Collections.sort() и TreeMap / TreeSet

Поиск элемента по значению из TreeMap и TreeSet занимает O(logN). В спецификации на Collections.sort() сказано, что в этом случае идет обращение к Arrays.sort() и получается O(N logN)
Вопрос: почему?
Я правильно понимаю, что причина в реализации TreeMap в виде черно-красного дерева, а сортированных коллекций - в виде обычного массива? Если да, то почему разница такая большая? Получается, что для поиска элемента по значению делается перебор всех элементов по порядку и сортировка всего лишь уменьшает возможное время на обработку каждого сравнения?

Ответ

Collections.sort принимает аргументом только коллекции, реализующие интерфейс List
public static > void sort(List list)
Поиск элемента и в красно-черном дереве и в отсортированном массиве можно осуществлять за O(logN), при условии что поиск в массиве будет происходить не методом indexOf, а бинарным поиском, с помощью Collections.binarySearch