de.ipcon.tools

Class IntIndexTimSort

java.lang.Object

de.ipcon.tools.IntIndexTimSort

public class IntIndexTimSort
extends java.lang.Object

A stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when running on partially sorted arrays, while offering performance comparable to a traditional mergesort when run on random arrays. Like all proper mergesorts, this sort is stable and runs O(n log n) time (worst case). In the worst case, this sort requires temporary storage space for n/2 object references; in the best case, it requires only a small constant amount of space. This implementation was adapted from Tim Peters's list sort for Python, which is described in detail here: http://svn.python.org/projects/python/trunk/Objects/listsort.txt Tim's C code may be found here: http://svn.python.org/projects/python/trunk/Objects/listobject.c The underlying techniques are described in this paper (and may have even earlier origins): "Optimistic Sorting and Information Theoretic Complexity" Peter McIlroy SODA (Fourth Annual ACM-SIAM Symposium on Discrete Algorithms), pp 467-474, Austin, Texas, 25-27 January 1993. While the API to this class consists solely of static methods, it is (privately) instantiable; a TimSort instance holds the state of an ongoing sort, assuming the input array is large enough to warrant the full-blown TimSort. Small arrays are sorted in place, using a binary insertion sort.

Author:

Josh Bloch Extracted from OpenJDK, sadly necessary as it's completely package private. Only difference is the capability to provide an information about a left 0-n area which is sorted already, to avoid another n sorts.

See Also:

flyingSort(int[], de.ipcon.tools.IntIndexComparator, int)

Method Summary

Modifier and Type	Method and Description
static void	flyingSort(int[] a, IntIndexComparator c, int knownSortedUntil) 'Flying start' version of @see #sort
static void	sort(int[] a, IntIndexComparator c) Sorts a given int array with the help of the IntIndexComparator.

Methods inherited from class java.lang.Object

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

Method Detail

sort

public static void sort(int[] a,
                        IntIndexComparator c)

Sorts a given int array with the help of the IntIndexComparator.

Parameters:

a - the array to be sorted

c - the comparator to use

flyingSort

public static void flyingSort(int[] a,
                              IntIndexComparator c,
                              int knownSortedUntil)

'Flying start' version of @see #sort

Parameters:

a - the array to be sorted

c - the comparator to use

knownSortedUntil - the index to which a is presorted

See Also:

TimSort.flyingSort(T[], java.util.Comparator<? super T>, int)