Java Arrays.sort() is safe now?

Правка en1, от AQZZ, 2020-06-09 07:04:33

I saw many articles saying that Java Arrays.sort() on int[] has worst case complexity O(n^2) but according to the Java docs:

" public static void sort(int[] a, int fromIndex, int toIndex) Sorts the specified range of the array into ascending order. The range to be sorted extends from the index fromIndex, inclusive, to the index toIndex, exclusive. If fromIndex == toIndex, the range to be sorted is empty. Implementation note: The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations. "

Does this mean that Arrays.sort() is safe to use now in Java? Does it also hold for Kotlin, or does Kotlin use a lower version of Java that still has the hack-vulnerable quick-sort?

Теги #java, #kotlin

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский AQZZ 2020-06-09 07:04:33 990 Initial revision (published)