title: Heap sort not working as expected
body: <p>I'm trying to implement heap sort using the CLRS book. My code is:</p>
  
  <pre><code>private void maxHeapify(int[] input, int i) {
      int l = left(i);
      int r = right(i);
      int largest;
  
      if(l &lt;= heapSize &amp;&amp; input[l] &gt; input[i]) {
          largest = l;
      } else {
          largest = i;
      }
  
      if(r &lt;= heapSize &amp;&amp; input[r] &gt; input[largest]) {
          largest = r;
      }
  
      if(largest != i) {
          swap(input, i, largest);
          maxHeapify(input, largest);
      }
  }
  
  private void buildMaxHeap(int[] input) {
      heapSize = input.length;
      for(int i = (input.length-1)/2; i &gt;= 0; i--) {
          maxHeapify(input, i);
      }
  }
  
  public void heapSort(int[] input) {
      buildMaxHeap(input);
  
      for(int i = input.length-1; i &gt; 0; i--) {
          swap(input, 0, i);
          heapSize--;
          maxHeapify(input, 0);
      }
  }
  </code></pre>
  
  <p>For an input of <code>{1, 5, 3, 7, 2, 0, 6, 2}</code>, I'm getting the answer as <code>7 3 0 6 2 5 1 2</code>. Why is this happening? I'm guessing it has something to do with the line <code>for(int i = (input.length-1)/2; i &gt;= 0; i--)</code> but I can't put my finger on it.</p>