Does the Collections.sort(list)
check if the list
is already sorted or is it maybe O(1) for some other reason?
Or, is it a good idea to have a flag sorted and set it to true
/false
upon calling sort()
/adding an element to the list?
sort() method is present in java. util. Collections class. It is used to sort the elements present in the specified list of Collection in ascending order.
Summary. Collections class sort() method is used to sort a list in Java. We can sort a list in natural ordering where the list elements must implement Comparable interface. We can also pass a Comparator implementation to define the sorting rules.
The sort method transfers control to the compare method, and compare method returns values based on the arguments passed: If both the objects are equal, returns 0. If the first object is greater than the second, returns a value > 0. If the second object is greater than the first, returns a value < 0.
How can you determine if any list is sorted without looking at it? It wont be O(1)
. Determining if a list is sorted takes at least O(n)
.
That would mean If Collections.sort
did bother to check if a list was sorted first each sorting operation would take an average of O(n) + O(n log n)
.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With