I need to execute another sorting for an array of 2 Million elements using Arrays.sort(..) method. In order not to keep another dirty flag like, I was wondering how costly is this method call for an already sorted array.
Any thoughts?
Asked
Active
Viewed 1,216 times
1
-
There's only one way to find out. – Shiva Jun 12 '14 at 16:32
-
See http://programmers.stackexchange.com/questions/232334/best-and-worst-case-for-the-quicksort-algorithm-with-7-elements (which is what sort uses) Keep your dirty flag. – dotnetnate Jun 12 '14 at 16:35
-
Shiva: You mean analysis of the algorithm? – NeplatnyUdaj Jun 12 '14 at 16:35
4 Answers
2
It depends on the content of your array. Sorting primitives uses a dual-pivot Quick Sort, as per the docs. This has an amortized complexity of O(n logn), though worst case is O(n^2)
Sorting Objects uses TimSort (docs), a modified Merge Sort. According to the docs, TimSort for a nearly-sorted (or, presumably, sorted) array takes approximately n comparisons.
It would be far cheaper still for you to keep a dirty flag rather than suffer the O(n) compares.
Avery
- 2,270
- 4
- 33
- 35
-
Finally, an answer that recognizes that `Arrays.sort()` is implemented differently for primitives and objects... I would say though that whether a dirty flag is useful really depends on what other things are going on. – awksp Jun 12 '14 at 17:13
0
For primitives arrays
Best case performance O(n log n)
Worst case performance O(n2)
For more detailed information read : http://en.wikipedia.org/wiki/Quicksort
For Object[] array
Worst case performance O(n log n)
Best case performance O(n)
For more detailed information read : http://en.wikipedia.org/wiki/Timsort
Community
- 1
- 1
Sergey Shustikov
- 15,377
- 12
- 67
- 119
-
`Arrays.sort()` only uses quicksort for primitives. Object arrays are sorted using mergesort. – awksp Jun 12 '14 at 17:12
-
-
@user3580294 Actually, it's not even really Merge Sort. It's TimSort: http://svn.python.org/projects/python/trunk/Objects/listsort.txt. – Avery Jun 12 '14 at 17:13
-
@Avery Which is a type of mergesort, as stated in the first sentence. But you're right. – awksp Jun 12 '14 at 17:14
-
-
1@deathember your TimSort worst case is wrong. It should be `O(N * log N)`. Source: http://en.wikipedia.org/wiki/Timsort#Performance – Avery Jun 12 '14 at 17:25
-1
Per this thread, the sorting runtime will be O(n*log n) since Arrays.sort() uses a modified version of quicksort, whether the array is already sorted or not.
-
1
-
@dotnetnate depends on if you're sorting primitives or objects. Sorting an array of objects uses Timsort (a type of mergesort), and sorting primitives uses quicksort. So worst case could in fact be O(n lg n) – awksp Jun 12 '14 at 16:45
-1
Array.sort() uses the best case complexity scenario of O(n log n) to sort an array by using Merge Sort which in turn uses divide and conquer approach. In the best case where you already have a sorted array the Best Possible Case could be O(n).
Purnima Nagpal
- 1
- 1
-
-
1Also, you're being contradictory. Does mergesort have best case O(n lg n) or O(n) complexity? Pick one. – awksp Jun 12 '14 at 16:55