title: C++ implementation of Iterative Merge Sort crashing at large input sizes due to stack overflow
body: <p>I don't have much experience with a stack overflow, i thought they were caused by recursive functions exceeding a certain recursion depth, why would they occur here in this iterative implementation of the merge sort!</p>
  
  <pre><code>    #include&lt;iostream&gt;
      #include &lt;stdlib.h&gt;
      #define SIZE 3000000
  
      int L[2500002];
      int R[2500002];
  
      using namespace std;
  
      int min(int a, int b) {
          return !(b&lt;a) ? a : b;
      }
  
      void Merge(int data[], int p, int q, int r)
      {
          if (q &gt;= SIZE)q = (r + p) / 2;
          int sizeL = q - p + 2;
          int sizeR = r - q + 1;
  
          for (int i = 0; i &lt; sizeL - 1; i++)
              L[i] = data[i + p];
          for (int i = 0; i &lt; sizeR - 1; i++)
              R[i] = data[i + q + 1];
  
          int max;
          if (L[sizeL - 2]&gt;R[sizeR - 2])
              max = L[sizeL - 2] + 1;
          else
              max = R[sizeR - 2] + 1;
          L[sizeL - 1] = R[sizeR - 1] = max;
  
          int indexL = 0, indexR = 0;
          for (int i = p; i &lt;= r; i++){
              if (L[indexL] &lt;= R[indexR]){
                  data[i] = L[indexL];
                  indexL++;
              }
              else{
                  data[i] = R[indexR];
                  indexR++;
              }
          }
  
  
      }
  
      void MergeSort(int data[], int p, int r)
      {
          for (int i = 1; i&lt; SIZE; i *= 2)
              for (int j = 0; j &lt; SIZE; j += 2 * i)
                  Merge(data, j, j + i - 1, min((j + 2 * i - 1), SIZE - 1));
      }
      /*****************************************************************************/
  
      bool IsSorted(int data[], int size)
      {
          int i;
  
          for (i = 0; i&lt;(size - 1); i++)
          {
              if (data[i] &gt; data[i + 1])
                  return false;
          }
          return true;
      }
  
      int main()
      {
          int data[SIZE];
          for (int i = 0; i &lt; SIZE; i++)
              data[i] = rand();
          MergeSort(data,0,SIZE-1);
          if(IsSorted(data, SIZE))
              cout &lt;&lt; "Sorted correctly";
          else
              cout &lt;&lt; "incorrect sorting";
          getchar();
          return 0;
      }
  </code></pre>