AQZZ's blog

By AQZZ, history, 4 years ago, In English

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?

  • Vote: I like it
  • +5
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

many != all