Why does Java’s Arrays.sort method use two different sorting algorithms for different types?

by

The most likely reason: quicksort is not stable, i.e. equal entries can change their relative position during the sort; among other things, this means that if you sort an already sorted array, it may not stay unchanged.

Since primitive types have no identity (there is no way to distinguish two ints with the same value), this does not matter for them. But for reference types, it could cause problems for some applications. Therefore, a stable merge sort is used for those.

OTOH, a reason not to use the (guaranteed n*log(n)) stable merge sort for primitive types might be that it requires making a clone of the array. For reference types, where the referred objects usually take up far more memory than the array of references, this generally does not matter. But for primitive types, cloning the array outright doubles the memory usage.

More Related Contents:

  1. How to merge two sorted arrays into a sorted array? [closed]
  2. Multithreaded quicksort or mergesort
  3. ‘MergeSort Algorithm’ – What’s the better implementation in JAVA? [closed]
  4. Mergesort in java
  5. Modulus of a very large number
  6. Fast algorithm to calculate n! / (q!)^r
  7. O(3^n) exponential time complexity [closed]
  8. Showing the order of growth of the function
  9. Good Java graph algorithm library? [closed]
  10. Sparse matrices / arrays in Java
  11. Natural sort order string comparison in Java – is one built in? [duplicate]
  12. Quickest way to find missing number in an array of numbers
  13. Java, find intersection of two arrays
  14. Calculating all of the subsets of a set of numbers
  15. Stack with find-min/find-max more efficient than O(n)?
  16. How to convert a byte array to its numeric value (Java)?
  17. Java – Removing duplicates in an ArrayList
  18. Parallel execution of directed acyclic graph of tasks
  19. Find top N elements in an Array
  20. How to generate a random permutation in Java?
  21. Java – Sort one array based on values of another array?
  22. In Java, how do I efficiently and elegantly stream a tree node’s descendants?
  23. How to generate the power-set of a given List?
  24. How to restore the PriorityQueue to its initial state before the method call?
  25. How to determine if binary tree is balanced?
  26. Determine the most common occurrence in an array
  27. What is the algorithm for finding the center of a circle from three points?
  28. Finding the shortest path nodes with breadth first search
  29. Time complexity of System.arraycopy(…)?
  30. StackOverflowError computing factorial of a BigInteger?

Leave a Comment