6

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?

Improve this question

4 Answers 4

Reset to default
9

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.sortdid bother to check if a list was sorted first each sorting operation would take an average of O(n) + O(n log n).

Improve this answer
2
  • 3
    strictly speaking, O(1) does not mean 1 index :)
    – unbeli
    Commented Apr 28, 2012 at 21:28
  • 6
    And O(n) + O(n log n) is the same as O(n log n) :)
    – unbeli
    Commented Apr 28, 2012 at 21:34
8

As a matter of fact with Java7, Java has switched from mergesort to TimSort (named after python dev Tim Peters who implemented it for cpython first) for some sorting tasks.

While it's not O(1), sorting an already sorted, or partially sorted list with TimSort is quite more efficient than sorting a completely random data set (for the later there's no way to be more efficient than O(n log n) for comparison sorts, that's not true for not random data).

Improve this answer
5
  • Ok, but the probability that the person who asked is using Java 7 is quite low (some say 18% blog.jelastic.com/2011/12/07/…)
    – Vitaly Olegovitch
    Commented Apr 28, 2012 at 21:47
  • 4
    @vitalik The probability that future readers will be using Java 7 or later can only increase from there. SO is intended as an archive of information, not a forum.
    – user207421
    Commented Apr 29, 2012 at 1:21
  • @EJP Considering that vitalik didn't downvote my post when he posted that comment, did you unintentionally misclick? Otherwise I'm quite surprised that anyone would downvote my post. b2t: I think as long as I explicitly mention that this is only true for Java7+ how many people are using whatever version isn't too important - 18% are still quite a lot of people.
    – Voo
    Commented Apr 29, 2012 at 9:34
  • The first comment looks so funny yet so obsolete in 2017 :)
    – ilyailya
    Commented Apr 12, 2017 at 8:47
  • 1
    @ilyailya Dunno - 18% Java 7 actually seems quite realistic these days ;)
    – Voo
    Commented Apr 12, 2017 at 16:48
3

There is no way it's O(1), you can't check if the collection is sorted faster than O(n). Having a flag should be fine, but hard to say for sure without knowing what exactly you are doing.

Improve this answer
2

Generally speaking, sorting an already sorted list doesn't make it faster (except simple sorts like bubble sort) In some cases pre-sorted is slower.

In the case of Collections.sort(), it is no faster to sort a sorted list.

Improve this answer
1
  • 4
    Actually not completely true. iirc Java is using Timsort for some things starting with Java7 and Timsort is quite good at sorting partially sorted lists, i.e. better than the theoretical O(n log n)
    – Voo
    Commented Apr 28, 2012 at 21:29

Not the answer you're looking for? Browse other questions tagged or ask your own question.