Java - Is calling sort() upon an already sorted list an O(1) operation?
java, sorting
Solution
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)`.
Problem
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?