The following code is an implementation of heapsort on an array
public static void heapSort(int[] inputArray){
/* Creates an array A which will contain the heap */
/* A has size n+1 to allow 1-based indexing */
int n = inputArray.length;
int[] A = new int[n+1];
int temp = 0;
/* Copies the array inputArray into A, with inputArray[i] being stored in A[i+1] */
for(int i=0; i<n; i++){
A[i+1] = inputArray[i];
}
constructHeap(A, n, 1);
removeMax(A, n);
copyBack(A, inputArray);
}
/* Transforms A into a max-heap using a 'bottom-up' algorithm. */
public static void constructHeap(int[] A, int n, int i){
if(2*i>n) return;
constructHeap(A, n, 2*i);
constructHeap(A, n, 2*i+1);
bubbleDown(A, n, i);
}
/*recursively swaps parent/child relationships until the max-heap property is satisfied. */
public static void bubbleDown(int[] A, int n, int i){
if(2*i>n) return;
int leftChild = 2*i;
int rightChild = 2*i+1;
int max = leftChild;
if(rightChild<=n && A[max]<A[rightChild]){
max = rightChild;
}
if(A[i]<A[max]){
int temp = A[i];
A[i] = A[max];
A[max] = temp;
bubbleDown(A, n, max);
}
}
/* Performs a sequence of n 'remove-maximum' operations, storing the removed element at
each step in successively smaller indices of A */
public static void removeMax(int[] A, int i){
for(int i=n; i>0; i--){
int temp = A[1];
A[1] = A[i];
bubbleDown(A, i, 1);
A[i] = temp;
}
/* Copies the sorted values in A back into inputArray, with inputArray[i] getting
the value from A[i+1] */
public static void copyBack(int[] A, int[] inputArray){
for(int i=0; i<inputArray.length; i++){
inputArray[i] = A[i+1];
}
}
StackOverflowException
gives a big clue. \$\endgroup\$ – David Harkness Mar 1 '14 at 21:54