title: Count number of steps heap sort takes to sort an array
body: <p>so I have been playing around with implementing "famous" sorting algorithms to see how many steps they take to sort an array. However I am stuck on Heapsort, I can't figure out how to count the steps properly. With my implementation, sorting a 128 long array takes 630 steps on average - which is a lot more than nlog(n). When sorting the same array with quicksort, it is around 260-280 which is almost exactly nlogn, this tells me that the counter for heapsort is wrong. Here is my current code:</p>
  
  <pre><code>    public static int heapify(double[] heap, int size, int index, bool asc, int steps)
      {
          int left = (index + 1) * 2 - 1;
          int right = (index + 1) * 2;
          int largest = 0;
          int stepCounter = steps;
          //For ascending sorting
          //Note: ideally there should be a maxHeapify for ascending and minHeapify for descending sorting seperately
          //however in this case it is easy to see what is happening
          if(asc)
          {
              if (left &lt; size &amp;&amp; heap[left] &gt; heap[index])
              {
                  largest = left;
              }
              else
              {
                  largest = index;
              }
  
              if (right &lt; size &amp;&amp; heap[right] &gt; heap[largest])
              {
                  largest = right;
              }
          } else
          {//For descending sorting
              if (left &lt; size &amp;&amp; heap[left] &lt; heap[index])
              {
                  largest = left;
              }
              else
              {
                  largest = index;
              }
  
              if (right &lt; size &amp;&amp; heap[right] &lt; heap[largest])
              {
                  largest = right;
              }
          }
  
          if (largest != index)
          {
              double temp = heap[index];
              heap[index] = heap[largest];
              heap[largest] = temp;
              stepCounter++;
              stepCounter = heapify(heap, size, largest, asc, stepCounter);
          }
          return stepCounter;
      }
      public static void heapSort(double[] heap, bool asc, int steps = 0)
      {
          int size = heap.Length;
          int i;
          int stepCounter = steps;
          //Build heap
          for (i = (size - 1) / 2; i &gt;= 0; i--)
          {
              stepCounter = heapify(heap, size, i, asc, stepCounter);
          }
  
          for(i = heap.Length - 1; i &gt; 0; i--)
          {
              double temp = heap[i];
              heap[i] = heap[0];
              heap[0] = temp;
              size--;
              stepCounter = heapify(heap, size, 0, asc, stepCounter);
          }
          Console.WriteLine("Heap sort has taken {0} steps", stepCounter);
      }
  </code></pre>
  
  <p>Thanks.
  To be clear: I only want one statement at the end, printing the number of all steps, rather than lots of messages for 2-3 steps each.</p>
  
  <p>edit:
  I changed around the code like so:</p>
  
  <pre><code>    public static int heapify(double[] heap, int size, int index, bool asc, int steps)
      {
  
          int stepCounter = 0;
  
          if (largest != index)
          {
              double temp = heap[index];
              heap[index] = heap[largest];
              heap[largest] = temp;
              stepCounter++;
              heapify(heap, size, largest, asc, stepCounter);
          }
          return stepCounter;
      }
      public static void heapSort(double[] heap, bool asc, int steps = 0)
      {
          int stepCounter = steps;
          //Build heap
          for (i = (size - 1) / 2; i &gt;= 0; i--)
          {
              stepCounter += heapify(heap, size, i, asc, stepCounter);
          }
  
          for(i = heap.Length - 1; i &gt; 0; i--)
          {
              double temp = heap[i];
              heap[i] = heap[0];
              heap[0] = temp;
              size--;
              stepCounter += heapify(heap, size, 0, asc, stepCounter);
          }
          Console.WriteLine("Heap sort has taken {0} steps", stepCounter);
      }
  </code></pre>
  
  <p>(deleted irrelevant bits). With this, I get 160-170 for 128 length arrays on average, and around 1300 steps for arrays of length ~1000. I think this sounds reasonable. Thank you @jdweng</p>