title: Iterative MergeSort Time Complexity (Bottom-Up)
body: <p>I have a problem with finding the time-complexity.</p>
  
  <ul>
  <li>Firtly, speaking about the outer FOR in MergeSort, i think that the repetitions are (1+ Sumation(from i=1, to sizeOfArray)(2*i) = 1+(2+4+8+16+32+...+size) but i also think that i am very wrong.</li>
  <li>I also have a problem measuring the inside FOR-loop repetitions.</li>
  </ul>
  
  <p><strong>MergeSort</strong>(){     //Iterative Version (Bottom-Up)</p>
  
  <pre><code>            for(int currentSize = 1; currentSize &lt; length; currentSize *= 2)        {
                  for(int low = 0; low &lt; length - currentSize; low += 2*currentSize){
  
                      int mid = low + currentSize - 1;
                      //min() is used here so if low is very close to the end of the array, high doesn't take outOfBoundries Value.
                      int high = Math.min(low + currentSize*2 -1, length - 1);
  
                  }
              }
  </code></pre>
  
  <p>}</p>
  
  <p><strong>merge</strong>(int low, int middle, int high) {</p>
  
  <pre><code>            // Copy both parts into the helper array
              for (int i = low; i &lt;= high; i++) {
                      helper[i] = arrayForMergeSort[i];
              }
  
              int i = low;
              int j = middle + 1;
              int k = low;
              // Copy the smallest values from either the left or the right side back
              // to the original array
              while (i &lt;= middle &amp;&amp; j &lt;= high) {
                      if (helper[i] &lt;= helper[j]) {
  
                              arrayForMergeSort[k] = helper[i];
                              i++;
                      } else {
  
                              arrayForMergeSort[k] = helper[j];
                              j++;
                      }
                      k++;
              }
              // Copy the rest of the left side of the array into the target array
              while (i &lt;= middle) {
                      arrayForMergeSort[k] = helper[i];
                      k++;
                      i++;
              }
  
      }
  </code></pre>