Search for an item by value from TreeMap and TreeSet is O(logN) . The specification for Collections.sort() says that in this case Arrays.sort() and O(N logN) .

Question: why?

I understand correctly that the reason for the implementation of TreeMap in the form of black and mahogany, and sorted collections - in the form of a regular array? If so, why is the difference so big? It turns out that in order to search for an element by value, the enumeration of all elements is done in order and sorting only reduces the possible time for processing each comparison?

    2 answers 2

    Collections.sort takes as an argument only collections that implement the List interface:

     public static <T extends Comparable<? super T>> void sort(List<T> list)

    You can also search for an element in a red-black tree and in a sorted array using O (logN), provided that the search in the array will not be performed by the indexOf method, but by binary search using Collections.binarySearch

      If I understand your question correctly, the answer is: you are right. TreeMap is a red-black tree, and Collections.sort() uses a different algorithm — merge sort. Arrays.sort() uses quicksort.