Snailclimb
是否有必要对Arrays.sort的源码在JDK1.7和JDK14的改动进行讲解？
如题，在JDK1.7和JDK14中分别对Arrays.sort()进行了实现上的改变，在JDK1.7引入了双枢纽元快速排序，在JDK14中通过Fork&Join框架引入了多线程归并排序、多线程双枢纽元快速排序、小数组的直接插入排序和混合插入排序、相对有序数组的堆排序，实现变得越来越复杂
如题，在JDK1.7和JDK14中分别对Arrays.sort()进行了实现上的改变，在JDK1.7引入了双枢纽元快速排序，在JDK14中通过Fork&Join框架引入了多线程归并排序、多线程双枢纽元快速排序、小数组的直接插入排序和混合插入排序、相对有序数组的堆排序，实现变得越来越复杂
hi，老哥，我觉得可以，你可以尝试提一个pr给我，你觉得如何？
Arrays is a class used for array object basic operation sort, min, max. Collections is a class used for collection framework objects basic operation but these collection object are basically container of wrapper class object these can't contain primitive objects.
Arrays is a class used for array object basic operation sort, min, max. Collections is a class used for collection framework objects basic operation but these collection object are basically container of wrapper class object these can't contain primitive objects.
@hokage123 说人话
数组是用于数组对象基本操作排序（最小值，最大值）的类。 集合是用于集合框架对象基本操作的类，但是这些集合对象基本上是包装器类对象的容器，它们不能包含原始对象。
数组是用于数组对象基本操作排序（最小值，最大值）的类。 集合是用于集合框架对象基本操作的类，但是这些集合对象基本上是包装器类对象的容器，它们不能包含原始对象。
@hokage123 我不是让你翻译，你说的这些和sort实现有啥关系？
After the Collection framework Arrays.sort() have not much changed but there should be some change in Collections. Sort() because of ArrayList<Type> means generic class concept
Both use quick sort implementation.
负责任的告诉你，对于对象类型根本没有使用快速排序，而对于基本类型也不是单纯使用快速排序，使用快速排序的时候使用的也不是传统的快速排序。
Responsibly tell you that don’t use quick sort for object types at all, and don’t just use quick sort for basic types, and don’t use traditional quick sort although using quick sort.
Both use quick sort implementation.
I will tell you responsibly that you don't use quick sort for object types at all, and you don't just use quick sort for basic types, and you don't use traditional quick sort when you use quick sort.
Responsibly tell you that don't use quick sort for object types at all, and don't just use quick sort for basic types, and don't use traditional quick sort although using quick sort.
Yes I know as collection are container of wrapper class they don't use traditional quick sort
Collections.sort(list) is just calling list.sort(). Dependencies on list.sort() implementation, ArrayList is just delegated to Arrays.sort(elements), both LinkedList after copying all elements to an object array. Without self implementing List.sort(), Collections.sort(list) just calls Arrays.sort(elements) indirectly
Both use quick sort implementation.
I will tell you responsibly that you don't use quick sort for object types at all, and you don't just use quick sort for basic types, and you don't use traditional quick sort when you use quick sort. Responsibly tell you that don't use quick sort for object types at all, and don't just use quick sort for basic types, and don't use traditional quick sort although using quick sort.
Yes I know as collection are container of wrapper class they don't use traditional quick sort
Not quick sort! All of objects but primitives and wrappers used TimSort( an optimization of merge sort )!
Both use quick sort implementation.
I will tell you responsibly that you don't use quick sort for object types at all, and you don't just use quick sort for basic types, and you don't use traditional quick sort when you use quick sort. Responsibly tell you that don't use quick sort for object types at all, and don't just use quick sort for basic types, and don't use traditional quick sort although using quick sort.
Yes I know as collection are container of wrapper class they don't use traditional quick sort
Not quick sort! All of objects but primitives and wrappers used TimSort( an optimization of merge sort )!
Got it!
'cause merge sort is suitable sort but quick sort not. In some reasons, you might want to sort twice but use different fields, and keep the first order, then you could not use quick sort ( it's not suitable ). But it's no problem when sort primitives and wrappers, because they have only one value!
But For using this or any sort on any wrapper class container it is needed to implement comparable interface and override compare to() or use Comparator interface. For eg Integer, Double, String etc all implements Comparable and override compare your().
'cause merge sort is suitable sort but quick sort not. In some reasons, you might want to sort twice but use different fields, and keep the first order, then you could not use quick sort ( it's not suitable ). But it's no problem when sort primitives and wrappers, because they have only one value! Duplicacy of key or something other than that
But For using this or any sort on any wrapper class container it is needed to implement comparable interface and override compare to() or use Comparator interface. For eg Integer, Double, String etc all implements Comparable and override compare your().
Not necessary, you could provide different Comparator for different sort case, like this: Arrays.sort(elements, comparator)
But For using this or any sort on any wrapper class container it is needed to implement comparable interface and override compare to() or use Comparator interface. For eg Integer, Double, String etc all implements Comparable and override compare your().
Not necessary, you could provide different
Comparatorfor different sort case, like this: `Arrays.sort(elements, comparator) Gotcha
Ouch! My mistake! For wrappers, it will use TimSort too. It just overrides primitives to use quick sort ( DualPivotQuickSort actually ).
所以，在单线程的双枢纽元快速排序，多线程归并排序、多线程双枢纽元快速排序、小数组的直接插入排序和混合插入排序、相对有序数组的堆排序，还有 TimSort 当中，当对象数组类型不同时，Arrays.sort() 到底是怎么选择的？
所以，在单线程的双枢纽元快速排序，多线程归并排序、多线程双枢纽元快速排序、小数组的直接插入排序和混合插入排序、相对有序数组的堆排序，还有 TimSort 当中，当对象数组类型不同时，Arrays.sort() 到底是怎么选择的？
简单说，视情况而定！最简单的判断方法就是判断元素是基本类型还是对象类型——对于基本类型使用不稳定的排序，而所有的对象类型都是用稳定的排序（因为Java的泛型擦除，所以没办法判断是不是包装类而改用不稳定排序）。
Simply, it depends! The easiest way to judge is to determine whether the element is a primitives type, use unstable sorting, and all object types are sorted with stability (because Java's generics erase, there is no way to judge whether it is wrapped Instead of unstable sorting).
顺便纠正下这个问题：堆排序并不是用于相对有序的! 常用的排序算法中，O(nlogn)的排序算法大多是基于分治法的，而这种情况下可能会因为递归深度过高而引发爆栈问题（即使是使用手动模拟栈），而堆排序是不需要递归的O(nlogn)排序算法，所以在递归深度足够深的时候会使用堆排序去替代基于递归的排序。
By a way, Heap-Sort is not used for nearly ordered array! Most of daily used O(nlogn) sorting algorithms are based Divide-Conquer Algorithm, it would trigger StackOverflow exception when deep recursion (even manually), but Heap-sort is recursion-free.
顺便纠正下这个问题：堆排序并不是用于相对有序的! 常用的排序算法中，O(nlogn)的排序算法大多是基于分治法的，而这种情况下可能会因为递归深度过高而引发爆栈问题（即使是使用手动模拟栈），而堆排序是不需要递归的O(nlogn)排序算法，所以在递归深度足够深的时候会使用堆排序去替代基于递归的排序。
By a way, Heap-Sort is not used for nearly ordered array! Most of daily used O(nlogn) sorting algorithms are based Divide-Conquer Algorithm, it would trigger StackOverflow exception when deep recursion (even manually), but Heap-sort is recursion-free.
But Heap Sort is a unstable one Tim Sort is stable one and Heap Sort usecases generally arise to find nth max min in logn time.
顺便纠正下这个问题：堆排序并不是用于相对有序的! 常用的排序算法中，O(nlogn)的排序算法大多是基于分治法的，而这种情况下可能会因为递归深度过高而引发爆栈问题（即使是使用手动模拟栈），而堆排序是不需要递归的O(nlogn)排序算法，所以在递归深度足够深的时候会使用堆排序去替代基于递归的排序。 By a way, Heap-Sort is not used for nearly ordered array! Most of daily used O(nlogn) sorting algorithms are based Divide-Conquer Algorithm, it would trigger StackOverflow exception when deep recursion (even manually), but Heap-sort is recursion-free.
But Heap Sort is a unstable one Tim Sort is stable one and Heap Sort usecases generally arise to find nth max min in logn time.
So Heap-Sort is never used in TimSort/TimComparableSort, just in DualPivotQuickSort