com.bluegosling.collections.sorting

Class SmoothSort

java.lang.Object

com.bluegosling.collections.sorting.SmoothSort

public final class SmoothSort
extends Object

Sorts arrays and collections using the Smoothsort algorithm. This algorithm is very similar to heap sort, but it uses a Leonardo heap instead of a binary heap. The way the Leonardo heap is represented in-place in the array (or list) enables sorting operations to take advantage of partially sorted data (data where there are runs of sorted elements). This gives the algorithm a linear best case.

Method Summary

Modifier and Type	Method and Description
static <T extends Comparable<? super T>> void	sort(List<T> list) Sorts the given list according to the elements' natural ordering.
static <T> void	sort(List<T> list, Comparator<? super T> comp) Sorts the given list according to the specified comparator.
static <T extends Comparable<? super T>> void	sort(T[] array) Sorts the given array according to the elements' natural ordering.
static <T> void	sort(T[] array, Comparator<? super T> comp) Sorts the given array according to the specified comparator.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

sort

public static <T extends Comparable<? super T>> void sort(List<T> list)

Sorts the given list according to the elements' natural ordering. This is equivalent to using Collections.sort(List), except it will utilize the smoothsort algorithm instead of Java's default implementation (mergesort in versions 6 and earlier, timsort in versions 7 and up).

Parameters:

list - the list which will be sorted in place

sort

public static <T> void sort(List<T> list,
                            Comparator<? super T> comp)

Sorts the given list according to the specified comparator. This is equivalent to using Collections.sort(List, Comparator), except it will utilize the smoothsort algorithm instead of Java's default implementation (mergesort in versions 6 and earlier, timsort in versions 7 and up).

Parameters:

list - the list which will be sorted in place

sort

public static <T extends Comparable<? super T>> void sort(T[] array)

Sorts the given array according to the elements' natural ordering. This is equivalent to using Arrays.sort(Object[]), except it will utilize the smoothsort algorithm instead of Java's default implementation (mergesort in versions 6 and earlier, timsort in versions 7 and up).

Parameters:

array - the array which will be sorted in place

sort

public static <T> void sort(T[] array,
                            Comparator<? super T> comp)

Sorts the given array according to the specified comparator. This is equivalent to using Arrays.sort(Object[], Comparator), except it will utilize the smoothsort algorithm instead of Java's default implementation (mergesort in versions 6 and earlier, timsort in versions 7 and up).

Parameters:

array - the array which will be sorted in place