title: Working of sorted() in java streams using lambda expression as comparator
body: <p>I have the following code: </p>
  
  <pre><code>        Stream.of("5", "1", "3", "4", "2", "6")
          .sorted((s1, s2) -&gt; {
              System.out.printf("sort: %s; %s\n", s1, s2);
              return s1.compareTo(s2);
          })
          .forEach(s -&gt; System.out.println("forEach: " + s));
  </code></pre>
  
  <p>where I am trying to sort the given elements in a custom order defined by lambda expression above in the code.
  The code works as expected. No surprises there. 
  But I am curious on how the sorted() works on my provided lambda.
  I put a print statement inside sorted() and I see following result:</p>
  
  <pre><code>sort: 3; 1
  sort: 3; 5
  sort: 3; 1
  sort: 4; 3
  sort: 4; 5
  sort: 2; 4
  sort: 2; 3
  sort: 2; 1
  sort: 6; 3
  sort: 6; 5
  forEach: 1
  forEach: 2
  forEach: 3
  forEach: 4
  forEach: 5
  forEach: 6
  </code></pre>
  
  <p>and this is not what I expected. 
  I see that 3 and 1 are compared twice. Why ? 
  I see that 6 is never compared with 1 2 and 4. Why again ?</p>
  
  <p>I cannot deduce any logic in this way of comparison. </p>
  
  <p>Did some research and learnt that sorted() uses merge sort internally. For given array merge sort will require 6 comparisons:</p>
  
  <pre><code>2  6
  4  6
  1  2
  3  4
  5  6
  </code></pre>
  
  <p>but above we see way more than 6 comparisons. So what is happening ? 
  In general how does sort() work with custom comparator ? </p>