title: Inversion Count Algorithm without using Merge Sort (c++)
body: <p>I've been struggling for a few days to come up with code that follows the pseudo-code below to count the number of inversions of an unsorted list of permutation numbers. I need the algorithm to run in O(nlogn) time but I can only think of a solution in O(n^2logn) time.</p>
  
  <p>More specifically I would like to know how to speed up the 2nd step by not using a nested for loop. I know there are other efficient algorithms (ie. merge-sort) that would work but I need to follow the steps of the psuedo-code.</p>
  
  <pre><code>Instance: An array A[1] . . . A[n], a permutation of n numbers 1, . . . , n
  Question: Calculate vector B[j] = |{A[i] : j &gt; i and A[i] &gt; A[j]}| (the same as 
            B[j] = |{i : j &gt; i and A[i] &gt; A[j]}|) B[j] is the number of element 
            larger than A[j] to the left of A[j] in t the array A. In other words, 
            the sum of the elements in B is equal to the number of inversions in 
            the permutation A[1] . . . A[n].
  (1) Initialize B[i] to 0.
  (2) For each even A[j] find elements with indices smaller than j that are by one larger
  than A[j]: increase B[j] by the number of such elements;
  (3) Divide each A[i] by 2 (in the integer sense);
  (4) Stop when all A[i] are 0.
  </code></pre>
  
  <p>The following is the code I have came up with so far:</p>
  
  <pre><code>long long numInversions = 0;     
  // number of elements that are zero in the array
  unsigned int zeros = 0;
  
  do {
  
     // solution will need to replace this nested
     // for loop so it is O(n) not O(n^2)
     for (int i = 0; i &lt; permNumber; i++){
  
             // checks if element is even
             if(array[i] % 2 == 0){
                    for (int j = i; j &gt;= 0; j--){
                           if (array[j] == array[i] + 1){
                                  numInversions++;
                           }
                   }
             }
  
        }
  
       // resets value of zeros for each pass
       zeros = 0;
  
       for (int k = 0; k &lt; permNumber; k++){
               array[k] = array[k] / 2;
               if (array[k] == 0)
                    zeros++;
  
  
        }
  
  } while(zeros != permNumber);
  </code></pre>
  
  <p>Note: The algorithm should return the number of inversions in the list, a scalar. The pseudo-code asks for an array, but in the end the elements of the array are summed to compute the inversion count.</p>
  
  <pre><code>Example: Consider a permutation (2, 3, 6, 1, 3, 5) with six inversions. The 
  above algorithm works as follows:
  2 4 6 1 3 5        (no pairs)                                  ÷2
  1 2 3 0 1 2 1 =    0: one '1' to left, 2: one 3 to left        ÷2
  0 1 1 0 0 1 1 =    0: two '1's to left, 0: two '1's to left    ÷2
  0 0 0 0 0 0        total: 6 pairs 
  </code></pre>