title: TreeSet vs ArrayList and sort
body: <p>I have a lot of String objects and I should somehow sort them. I desided to to figure out what is more effective - put objects into TreeSet, so TreeSet sort objects by itself, or put objects in ArrayList and then sort ArrayList.</p>
  
  <p>I think with way: </p>
  
  <p>Good sort for ArrayList size N would has complexity of N * log(N).</p>
  
  <p>TreeSet use red-black binary tree for sorting. The complexity of insert for this structure is log(A) after A inserts. So complexity of insert of the first element would be equal log(1), complexity of insert of the second element would be equal log(2), and so on. So full complexity would be log(1) + log(2) + log(N). And this sum is less than N * log(N).</p>
  
  <p>So I expected that TreeSet would be more effective then ArrayList. </p>
  
  <p>I test it with code. This is it:</p>
  
  <pre><code>public class SortTest {    
      static String getRandomString() {
          Random random = new Random();
          String result = "";
          for (int i = 0; i &lt; 10; i++) {
              result += (char)(80 + random.nextInt(40));
          }
          return result;
      }
  
      static void testTreeSet() {
          TreeSet&lt;String&gt; treeSet = new TreeSet&lt;&gt;();
          for (int i = 0; i &lt; 10000000; i++) {
              treeSet.add(getRandomString());
          }
      }
  
      static void testArrayList() {
          ArrayList&lt;String&gt; arrayList = new ArrayList&lt;&gt;();
          for (int i = 0; i &lt; 10000000; i++) {
              arrayList.add(getRandomString());
          }
          Collections.sort(arrayList);
      }
  
      public static void main(String[] args) {
          Date date1 = new Date();
          testTreeSet();
          Date date2 = new Date();
          System.out.println(date2.getTime() - date1.getTime());        
          Date date3 = new Date();
          testArrayList();
          Date date4 = new Date();
          System.out.println(date4.getTime() - date3.getTime());
      }
  }
  </code></pre>
  
  <p>And I get this result:</p>
  
  <pre><code>23613
  16217
  </code></pre>
  
  <p>So ArrayList and sort is more effective than TreeSet.
  Can someone explain why?</p>