title: c++ comparator sorting using auxillary array
body: <p>I have an array (say <code>values</code>) that that cannot be modified. I want to know if the values in this array are sorted what will be their eventual position/index. So, for this I am simply using code as below:</p>
  <pre><code>#include &lt;iostream&gt;
  #include &lt;algorithm&gt;
  #include &lt;vector&gt;
  #include &lt;numeric&gt;
  
  int main() {
      std::vector&lt;unsigned&gt; position(11, 0);
      std::iota(position.begin(), position.end(), 0);
      std::vector&lt;unsigned&gt; values = {140, 141, 118, 119, 122, 123, 128, 129, 133, 134, 138, 139};
      
      auto value_comparator = [&amp;values](const unsigned&amp; index1, const unsigned&amp; index2) {
          return (values[index1] &lt; values[index2]);
      };
      
      std::sort(position.begin(), position.end(), value_comparator);
      
      for (auto val : position) {
          std::cout &lt;&lt; val &lt;&lt; &quot; &quot;;
      }
      std::cout &lt;&lt; std::endl;
  
      return 0;
  }
  </code></pre>
  <p><strong>Actual Output</strong>:</p>
  <pre><code>2 3 4 5 6 7 8 9 10 0 1
  </code></pre>
  <p><strong>Expected Output</strong>:</p>
  <pre><code>10 11 0 1 2 3 4 5 6 7 8 9
  </code></pre>
  <p>I am trying to understand why the output is as shown above. Looks like STL uses <code>IntroSort</code>. Looking for some input before I dig deeper.</p>
  <p>Thanks.</p>