Why does Collections.sort use Mergesort but Arrays.sort does not?

by

The API guarantees a stable sorting which Quicksort doesn’t offer. However, when sorting primitive values by their natural order you won’t notice a difference as primitive values have no identity. Therefore, Quicksort can used for primitive arrays and will be used when it is considered more efficient¹.

For objects you may notice, when objects with different identity which are deemed equal according to their equals implementation or the provided Comparator change their order. Therefore, Quicksort is not an option. So a variant of MergeSort is used, the current Java versions use TimSort. This applies to both, Arrays.sort and Collections.sort, though with Java 8, the List itself may override the sort algorithms.

¹ The efficiency advantage of Quicksort is needing less memory when done in-place. But it has a dramatic worst case performance and can’t exploit runs of pre-sorted data in an array, which TimSort does.

Therefore, the sorting algorithms were reworked from version to version, while staying in the now-misleadingly named class DualPivotQuicksort. Also, the documentation didn’t catch up, which shows, that it is a bad idea in general, to name an internally used algorithm in a specification, when not necessary.

The current situation (including Java 8 to Java 11) is as follows:

  • Generally, the sorting methods for primitive arrays will use Quicksort only under certain circumstances. For larger arrays, they will try to identify runs of pre-sorted data first, like TimSort does, and will merge them when the number of runs does not exceed a certain threshold. Otherwise they will fall back to Quicksort, but with an implementation that will fall back to Insertion sort for small ranges, which does not only affect small arrays, but also quick sort’s recursion.
  • sort(char[],…) and sort(short[],…) add another special case, to use Counting sort for arrays whose length exceeds a certain threshold
  • Likewise, sort(byte[],…) will use Counting sort, but with a much smaller threshold, which creates the biggest contrast to the documentation, as sort(byte[],…) never uses Quicksort. It only uses Insertion sort for small arrays and Counting sort otherwise.

More Related Contents:

  1. Lambda expression to convert array/List of String to array/List of Integers
  2. java: Arrays.sort() with lambda expression
  3. Difference between Arrays.sort() and Arrays.parallelSort()
  4. Assign information to element in array in java [closed]
  5. Java sort 4 arrays into 1 array
  6. Sorted array in Java: how can I implement? [closed]
  7. Converting ‘ArrayList to ‘String[]’ in Java
  8. Why is there no SortedList in Java?
  9. Java Array Sort descending?
  10. Sort a Map by values
  11. Collections.sort with multiple fields
  12. How can I get the size of an array, a Collection, or a String in Java?
  13. Java 8 stream reverse order
  14. Why does my sorting loop seem to append an element where it shouldn’t?
  15. Android-java- How to sort a list of objects by a certain value within the object
  16. How do I keep the iteration order of a List when using Collections.toMap() on a stream?
  17. Is it faster to add to a collection then sort it, or add to a sorted collection?
  18. How do I make 2 comparable methods in only one class?
  19. Java: how to convert HashMap to array
  20. Print array without brackets and commas
  21. Sort a parallel array using Arrays.sort()
  22. The easiest way to transform collection to array?
  23. How to use Collections.sort() in Java?
  24. Automatically sorted by values map in Java
  25. Sorting int array in descending order [duplicate]
  26. Java Sorting: sort an array of objects by property, object not allowed to use Comparable
  27. Perform operation on n random distinct elements from Collection using Streams API
  28. Group sequences of values
  29. Java 8 stream map to list of keys sorted by values
  30. How to convert Integer[] to int[] array in Java?

Leave a Comment