title: Algorithm that sorts a permutation
body: <p>I am stuck at this problem:</p>
  
  <hr>
  
  <p>Given a permutation P of {0,1,2,...,n-1} <br/>
  (Here n = P . length)</p>
  
  <p>Explain why the following algorithm sorts the permutation in increasing order and give a worst case scenario (pseudo-code)</p>
  
  <pre><code>PermutationSort(P)
      for i = 0 to P.length - 1
          while(P[i] != i)
              t = P[i]
              exchange P[i] with P[t]
  </code></pre>
  
  <p>(C++ code)</p>
  
  <pre><code>void PermutationSort(int P[], int len)
  {
      for(int i = 0; i &lt; len; i++)
          while(P[i] != i)
          {
              int tmp;
              tmp = P[i];
              P[i] = P[tmp];
              P[tmp] = tmp;
          }
  }
  </code></pre>
  
  <hr>
  
  <p>I am totally don't know why it sorts the permutation P.</p>
  
  <p>I've sat on this problem all day and I'm still don't get <strong>why</strong> it sorts the permutation.</p>
  
  <p>what "exchange P[i] with P[P[i]]" does and why we will ultimately get P[i] = i which will then terminate the inner loop?</p>
  
  <p>Thanks for any hint or help.</p>