Is Java 7 using Tim Sort for the Method Arrays.Sort?

by

Java 7 uses Dual-Pivot Quicksort for primitives and TimSort for objects.

According to the Java 7 API doc for primitives:

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.

According to the Java 7 API doc for objects:

The implementation was adapted from
Tim Peters’s list sort for Python (
TimSort). It uses techiques from Peter
McIlroy’s “Optimistic Sorting and
Information Theoretic Complexity”, in
Proceedings of the Fourth Annual
ACM-SIAM Symposium on Discrete
Algorithms, pp 467-474, January 1993.

Timsort is a hybrid “merge sort and insertion sort.”

Not sure if this is much different from what it was in Java 6, for Arrays.sort JDK6:

a tuned quicksort, adapted from Jon L.
Bentley and M. Douglas McIlroy’s
“Engineering a Sort Function”,
Software-Practice and Experience, Vol.
23(11) P. 1249-1265 (November 1993)

For Object[] or collections (Collections.sort()) merge sort is used.

More Related Contents:

  1. Write a function that will sort a string array using Java
  2. Assign information to element in array in java [closed]
  3. Java sort 4 arrays into 1 array
  4. Sorted array in Java: how can I implement? [closed]
  5. Java Array Sort descending?
  6. java Arrays.sort 2d array
  7. Sort a two dimensional array based on one column
  8. How to sort an array of objects in Java?
  9. Java, find intersection of two arrays
  10. Why does my sorting loop seem to append an element where it shouldn’t?
  11. Sorting 2D array of strings in Java
  12. Why does Collections.sort use Mergesort but Arrays.sort does not?
  13. Sort ArrayList of Array in Java
  14. How to check if array is already sorted
  15. Sort a parallel array using Arrays.sort()
  16. How do I sort two arrays in relation to each other?
  17. How to sort an array of objects containing null elements?
  18. Sorting int array in descending order [duplicate]
  19. java: Arrays.sort() with lambda expression
  20. Difference between Arrays.sort() and Arrays.parallelSort()
  21. Java Sorting: sort an array of objects by property, object not allowed to use Comparable
  22. int[] array (sort lowest to highest)
  23. Sorting two arrays simultaneously
  24. Check if an array is sorted, return true or false
  25. How to find size/length of an array without using library functions/variables [closed]
  26. Can I pass an array as arguments to a method with variable arguments in Java?
  27. Generic array creation error
  28. Remove duplicates from integer array
  29. What is the sorting algorithm for Java [closed]
  30. Flatten nested arrays in java

Leave a Comment