title: Sorting Test in Java -
body: <p>During the last months I created in Java some classes implementing data structures, more specifically Lists, Binary Search Trees and Binary Heaps. I decided to make a stress test by creating an <code>Integer</code>  array of <code>n</code> values between <code>0</code> and <code>10*n</code>, then sorting in various ways and measuring the times. </p>
  
  <p>Initially it was just a curiosity. Obviously I expected my classes to costs far more than the normal <code>Arrays.sort()</code> method. However when I did the tests and compared my classes against each other I found some unexpected surprises. </p>
  
  <p>This is the list of the tests, with details and comments.</p>
  
  <p><b>1.</b> A copy of the array is created, then the copy is sorted using the <code>Arrays.sort()</code> method, native of Java. <br> The time evaluated is that of the <code>Arrays.sort()</code> method, i.e. the creation of the copy of the array doesn't count. <br> It is <b>the fastest way</b>, as expected.</p>
  
  <p><p></p>
  
  <p><b>2.</b> A list is created from the array, then the list is sorted using the <i>Insertion Sort</i> algorithm. <br> The time evaluated is that of the sorting method, i.e. the creation of the list from the array doesn't count. <br> Since the performance of Insertion Sort is not exactly great, this method costs around <b>50 times the array method</b>.
  <p><b>3.</b> A Binary Search Trees (<code>BST</code> from now on) is created from the array repeating the <code>add()</code> method. <br> The <code>BST</code> is not a balanced tree like the AVL or the Red-Black, merely a normal <code>BST</code> like found on Wikipedia: every node has links to three other nodes (<code>parent</code>, <code>leftChild</code> and <code>rightChild</code>), incapsulates a <code>value</code>, etc... <br> This method costs arount <b>500 times the list method</b>, i.e. <b>25 000 times the array method</b>.
  <p><b>4-5.</b> Two Binary Heap (<code>BH_1</code> and <code>BH_2</code> from now on) are created from the array repeating the <code>add()</code> method, then they are converted into two (sorted) array repeating the <code>extractMin()</code> method. Both <code>BH</code> belongs to the same class and stores the value in a <code>Vector&lt;Integer&gt;</code>. Both <code>BH</code> costs around <b>2 times the BST</b> and <b>50 000 times the array method</b>. However there is a twist. <br> 
  <code>BH_2</code> creates the array using the method <code>convertHeapToArray()</code> of the <code>Heap&lt;Integer&gt;</code> interface. <code>convertHeapToArray()</code> calls the method <code>extractMin()</code> for <code>n</code> times, while <code>extractMin()</code> in turn calls the method <code>heapify()</code> one time.<br>
  This doesn't happen in <code>BH_1</code>, which uses the method <code>convertHeapToArray_1()</code>. Instead of calling <code>extractMin()</code>, my "new" method directly executes the code of <code>extractMin()</code> - and when <code>extractMin()</code> calls the method <code>heapify()</code>, <code>BH_1</code> instead executed its code. In short, a copy-paste that avoids a few calls.
  <br> In theory <code>BH_1</code> should always costs less than <code>BH_2</code>: same input data, same code, less method calling. <b>However this is true only 73% of the times!</b></p>
  
  <p>My questions are the following:</p>
  
  <p><b>1.</b> Why the Binary Search Trees sorting method (computational complexity <code>n log(n)</code>, expected to be balanced if created by <code>add()</code> only) costs <b>500 times</b> an Insertion Sort (computational complexity <code>n</code><sup>2</sup>, is preferable if <code>n</code> is less than 23)
  <p><b>2.</b> Why the Binary Heaps (same computational complexity of Binary Search Trees, specifically designed to sort quickly) costs <b>2 times</b> a Binary Search Trees?
  <p><b>3.</b> And, more baffling than ever, why making less calls is <b>more costly</b> than making more calls in <i>one case out of 4</i>?!</p>
  
  <hr>
  
  <p><b>Code for <code>convertHeapToArray()</code>:</b></p>
  
  <pre><code>    public default T[] convertHeapToArray(){
          T[] output = AArrays.createTarray(length(), min());
  
          for(int i=0 ; i&lt;length() ; i++)
              output[i] = this.extractMin();
          return output;
      }
  public T extractMin() {
      T min = storer.get(indexOfMinimum);
      AVector.swap(storer, indexOfMinimum, length);
      AVector.swap(storer, indexOfMinimum, length);
      length--;
      heapify(indexOfMinimum);
      return min;
  }
  </code></pre>
  
  <p><b>Report (5000 tests, 100 random arrays each):</b></p>
  
  <pre><code>The array use a Comparator&lt;Integer&gt;.
   A Comparator&lt;Integer&gt; executes a confront in 66083 nanoseconds.
  The list use a Comparator&lt;NodeList&lt;Integer&gt;&gt;.
   A Comparator&lt;NodeList&lt;Integer&gt;&gt; executes a confront in 85973 nanoseconds.
  The BST, BH_1 and BH_2 use a Relationship&lt;Integer&gt;.
   A Relationship&lt;Integer&gt; executes a confront in 107145 nanoseconds.
  
  The total time for the array sorting is 239 717 392 nanoseconds.
  The total time for the list sorting is 984 872 184 nanoseconds.
  The total time for the BST sorting is 533 338 808 811 nanoseconds.
  The total time for the BH_1 sorting is 1 055 836 440 689 nanoseconds.
  The total time for the BH_2 sorting is 1 198 365 741 676 nanoseconds.
  
  The medium time for the array sorting is 47 943 nanoseconds.
  The medium time for the list sorting is 196 974 nanoseconds.
  The medium time for the BST  sorting is 106 667 761 nanoseconds.
  The medium time for the BH_1 sorting is 211 167 288 nanoseconds.
  The medium time for the BH_2 sorting is 239 673 148 nanoseconds.
  The first method for the Binary Heap has been faster than the second for 3 634 times out of 5 000.
  </code></pre>
  
  <hr>
  
  <p><b>EDIT:</b></p>
  
  <p>Re-reading what I wrote, I realized I wasn't exactly clear in my initial question. Allow me to rectify my mistake.</p>
  
  <p>I am aware that there is a difference between the actual time executed by the program and the computational complexity. I never had any doubt on the computational complexity of the methods used: the data structures are simple, their code is pratically taken from Wikipedia . I was certain that the written code was not well performing. It wasn't written with performance <i>to begin with</i>.</p>
  
  <p>My test is on the actual time of execution. The <code>Arrays.sort()</code> method was included as a reference parameter. Since I didn't wrote the code with performance in mind, I suspected before the test that the results would be more costly than expected. However my prediction on <i>what</i> exactly was costing more than it should were thrown into the garbage bin by the results.</p>
  
  <p>For example I believed that less method calls would results in a lesser cost, <i>but I was wrong</i>. The whole difference between the two Binary Heaps was that the first executed the same code of the second, just with less method calls (minimal code for the BinaryHeap included below). I expected that the first Binary Heap would always have a lesser cost: this was proven wrong, and I don't know <i>why</i>.</p>
  
  <p>Another thing that baffled me was the fact that the Binary Heap costed more than the <code>Binary Search Tree</code>. The array used is created randomly. While with this starting condition the height of a Binary Search Tree is expected to be around <code>log(n)</code> (chapter 12, paragraph 4 of <i>Introduction to Algorithm</i>, by Cormen, Leiserson, Rivest, Stein), I never heard of an algorithm using Binary Search Trees to sort arrays: I included it in my test only as a curiosity. And yet for the small number of elements (initially 100) the Binary Search Trees was found consistently quicker than the Binary Heap. </p>
  
  <p>Why this happens? When a Binary Heap starts being more convenient? Was including the conversion Heap»Array a mistake?</p>
  
  <p>A <i>third</i> unexpected result  is the performance of the double-linked <code>List</code>. As with the Binary Search Trees, I included in the test as a curiosity. The sorting algorithm is a very basic Insertion Sort, which is faster only for a number of element far less than what I used, and the code of the entire class is most definitively not created for quickness. I supposed it would have revealed as the most slow of my classes, instead <i>it was the quickest!</i> And I still don't know <i>why</i>.</p>
  
  <p>This is why I asked advice. I didn't included the code because between all the classes it is around the ~3000 lines of code, most of which is unused by the test. <b>I</b> would not have read 3k lines of code, nor I expected the random stackoverflow-er to do so! However I included the code for the <code>BinaryHeap&lt;T&gt;</code>, which is ~300 lines.</p>
  
  <p><hr>
  <b>Code for <code>BinaryHeap&lt;T&gt;</code> : </b></p>
  
  <pre><code>public class BinaryHeap&lt;T&gt; implements Heap&lt;T&gt; {
      private static final int indexOfMinimum = 1;
      private Vector&lt;T&gt; storer = new Vector&lt;T&gt;(indexOfMinimum + 10);
      private Relationship&lt;T&gt; relationship = null;
      // The class Relationship&lt;T&gt; has a single method whose signature is 
      // public boolean confront(T a, T b);
      // The reason I included it instead of a Comparator is that, in my code, the value null represents -∞
      // 
      // The following code works.
      // 
      // public class Relationship&lt;T&gt;{
      //  Comparator&lt;T&gt; c;
      //  public Relationship&lt;T&gt;(Comparator&lt;T&gt; c){    this.c = c; }
      //  public boolean confront(T a, T b){  return a==null ? true : c.compare(a,b); }
      // }
  
      // TODO | Constructors
  
      public BinaryHeap(Relationship&lt;T&gt; relationship){
          storer.add(null);
          this.relationship = relationship;
      }
  
      // TODO | Methods of the interface Heap
  
      public void add(T newData) {
          storer.add(null);
          updateValue(storer.size() - 1, newData);
      }
      public T extractMin() {
          T min = storer.get(indexOfMinimum);
          heapify(indexOfMinimum);
          return min;
      }
      public void updateValue(int indexOfToBeUpgraded, T newValue) {
          int i = indexOfToBeUpgraded;
          T support;
          if( i &gt;= indexOfMinimum )
              {
              storer.set(i, newValue);
              while( i &gt; indexOfMinimum &amp;&amp; ! relationship.confront(storer.get(i/2), storer.get(i)) )
                  {
                  support = storer.get(i);
                  storer.set(i, storer.get(i/2));
                  storer.set(i, support);
                  i = i/2;
                  }
              }
      }
      private void heapify(int i){
          int j = i;
          int maximumIndexOfArray = storer.size();
          while( j &lt;= maximumIndexOfArray/2 )         // i.e. if H[j] isn't a leaf of the Tree
              {
              int indexOfLocalMinimum =   relationship.confront(storer.get(j),    storer.get(2*j))                        
                          ?   (   relationship.confront(storer.get(  j), storer.get(2*j+1))   ?     j : 2*j+1 )
                          :   (   relationship.confront(storer.get(2*j), storer.get(2*j+1))   ?   2*j : 2*j+1 )   ;
              if( j != indexOfLocalMinimum )
                  {
                  AVector.swap(storer, j, indexOfLocalMinimum);
                  j = indexOfLocalMinimum;
                  }
              else j = maximumIndexOfArray;
              }
      }
      public default T[] convertHeapToArray(){
      T[] output = (T[]) Array.newInstance(min().getClass(), length());
          for(int i=0 ; i&lt;length() ; i++)
              output[i] = this.extractMin();
          return output;
      }
  
      // TODO | Second version of the method convertHeapToArray, found out not to be improved
  
      public T[] convertHeapToArray_1(){
          int length = length(), j;
      T[] output = (T[]) Array.newInstance(min().getClass(), length());
          for(int i=0 ; i&lt;length ; i++)
              {
      //      output[i] = this.extractMin();
                  output[i] = storer.get(indexOfMinimum);
          //      heapify(indexOfMinimum);
                      j = indexOfMinimum;
                      int maximumIndexOfArray = storer.size();
                      while( j &lt;= maximumIndexOfArray/2 )         // i.e. if H[j] isn't a leaf of the Tree
                          {
                          int indexOfLocalMinimum =   relationship.confront(storer.get(j),    storer.get(2*j))                        
                                      ?   (   relationship.confront(storer.get(  j), storer.get(2*j+1))   ?     j : 2*j+1 )
                                      :   (   relationship.confront(storer.get(2*j), storer.get(2*j+1))   ?   2*j : 2*j+1 )   ;
                          if( j != indexOfLocalMinimum )
                              {
                              AVector.swap(storer, j, indexOfLocalMinimum);
                              j = indexOfLocalMinimum;
                              }
                          else j = maximumIndexOfArray;
                          }
                  }
          return output;
      }
  </code></pre>