Quicksort
Quicksort is an unstable O(n log n) average-case sorting algorithm. It works
by defining a pivot and swapping elements so that
lesser values appear before
the pivot and greater values appear after the pivot. The remaining pivots are
sorted recursively. As of Java 7, quicksort is the
default implementation for
sorting primitives in the Arrays class.
Timsort
Timsort is a stable O(n log n) average-case sorting algorithm. Timsort
is a hybrid algorithm derived from merge sort and insertion sort. It works
by identifying runs of naturally sorted data or by using
insertion sort to create
runs of a minimum size. The runs are merged together in the same manner
as merge sort. Timsort often performs far fewer than O(n log n)
comparisons because it takes advantage of partially sorted values. As of Java 7,
Timsort is the default implementation for sorting
objects in the Arrays and
Collections
classes.
