Heapsort is one of the best general-purpose sorting algorithms, a comparison sort and part of the selection sort family. Although somewhat slower in practice on most machines than a good implementation of quicksort, it has the advantages of worst-case O(n log n) runtime and being an in-place algorithm. Heapsort is not a stable sort.

The following code shows how to implement heap sort in Java.

 ``` /** * Standard heapsort. * @param a an array of Comparable items. */ public static void heapsort( Comparable [ ] a ) { for( int i = a.length / 2; i >= 0; i-- ) /* buildHeap */ percDown( a, i, a.length ); for( int i = a.length - 1; i > 0; i-- ) { swapReferences( a, 0, i ); /* deleteMax */ percDown( a, 0, i ); } } /** * Internal method for heapsort. * @param i the index of an item in the heap. * @return the index of the left child. */ private static int leftChild( int i ) { return 2 * i + 1; } /** * Internal method for heapsort that is used in * deleteMax and buildHeap. * @param a an array of Comparable items. * @index i the position from which to percolate down. * @int n the logical size of the binary heap. */ private static void percDown( Comparable [ ] a, int i, int n ) { int child; Comparable tmp; for( tmp = a[ i ]; leftChild( i ) < n; i = child ) { child = leftChild( i ); if( child != n - 1 && a[ child ].compareTo( a[ child + 1 ] ) < 0 ) child++; if( tmp.compareTo( a[ child ] ) < 0 ) a[ i ] = a[ child ]; else break; } a[ i ] = tmp; } /** * Method to swap to elements in an array. * @param a an array of objects. * @param index1 the index of the first object. * @param index2 the index of the second object. */ public static final void swapReferences( Object [ ] a, int index1, int index2 ) { Object tmp = a[ index1 ]; a[ index1 ] = a[ index2 ]; a[ index2 ] = tmp; } ```