Implementation of HeapSort 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&lt;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&gt;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&gt;n) return;
    int leftChild = 2*i;
    int rightChild = 2*i+1;
    int max = leftChild;
    if(rightChild&lt;=n &amp;&amp; A[max]&lt;A[rightChild]){
        max = rightChild;
    }
    if(A[i]&lt;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&gt;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&lt;inputArray.length; i++){
        inputArray[i] = A[i+1];
    }
}
Your constructHeap method works in O(n), and you call in O(n) times from removeMax method, so your code works in O(n^2), so it is not a correct implementation of Heapsort.

Comments:

public static void heapSort(int[] inputArray) {


Why do you need another array? Heapsort is in-place.

  /* Creates an array A which will contain the heap */


Why do you need 1-based indexing? You don't seem to use it anywhere, and 0-based is more convenient.

  /* A has size n+1 to allow 1-based indexing */
  int n = inputArray.length;


  int[] A = new int[n + 1];


You don't use this variable.

  int temp = 0;

  /* Copies the array inputArray into A, with inputArray[i] being stored in A[i+1] */


You should replace this loop with System.arraycopy(...) call

  for (int i = 0; i &lt; n; i++) {
    A[i + 1] = inputArray[i];
  }
  constructHeap(A, n, 1);
  removeMax(A, n);
  copyBack(A, inputArray);
}


Consider transforming such comments into valid javadoc.

/* Transforms A into a max-heap using a 'bottom-up' algorithm. */
public static void constructHeap(int[] A, int n, int i) {
  if (2 * i &gt; n) {
    return;
  }
  constructHeap(A, n, 2 * i);
  constructHeap(A, n, 2 * i + 1);
  bubbleDown(A, n, i);
}


Comment?

public static void bubbleDown(int[] A, int n, int i) {
  if (2 * i &gt; n) {
    return;
  }
  int leftChild = 2 * i;
  int rightChild = 2 * i + 1;
  int max = leftChild;
  if (rightChild &lt;= n &amp;&amp; A[max] &lt; A[rightChild]) {
    max = rightChild;
  }
  if (A[i] &lt; 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) {
  if (i == 0) {
    return;
  }
  int temp = A[1];
  A[1] = A[i];
  constructHeap(A, i, 1);
  A[i] = temp;


So you make O(n) recursive calls? This is causing StackOverflowException with large n and harming your running time. Consider transforming this tail recursion into a loop.

  removeMax(A, i - 1);
}

  /* 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) {


ditto

  for (int i = 0; i &lt; inputArray.length; i++) {
    inputArray[i] = A[i + 1];
  }
}