I am sorting resultsets via an integer key using TreeMap. Does anyone know the O-notation for the data structure in TreeMap which is a sorted Map ADT. Thanks Gavin
posted 15 years ago
If you are using the Collections.sort() method, then this quote from the API will answer your question:
The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n log(n) performance, and can approach linear performance on nearly sorted lists.