title: Sequential Merge Sort in C
body: <p>I am trying to re-write a recursive Merge Sort like</p>
  
  <pre><code>void MergeSort(int* data, int size){
    int half=size/2;
    if (size &gt; 1) {
      MergeSort(data, half);
      MergeSort(data+half, half);
      Merge(data, size);
    }
  }
  </code></pre>
  
  <p>in which</p>
  
  <pre><code>void Merge(int* data, int size){
    int cnt;
    int cntLow=0;
    int half=size/2;
    int cntHigh=half;
    int* sorted;
  
    sorted = (int*) malloc(size*sizeof(int));
  
    for (cnt=0; cnt&lt;size; cnt++){
      if (cntLow == half) 
        sorted[cnt] = data[cntHigh++];
      else if (cntHigh == size)
        sorted[cnt] = data[cntLow++];
      else if (data[cntLow] &lt;= data[cntHigh])
        sorted[cnt] = data[cntLow++];
      else
        sorted[cnt] = data[cntHigh++];
    }
  
    for (cnt=0; cnt&lt;size; cnt++)
      data[cnt] = sorted[cnt];
  
    free(sorted);
  }
  </code></pre>
  
  <p>to a non-recursive call. So I wrote the function</p>
  
  <pre><code>void MergeSort_NonRecursive(int* data, int size){
      int i;
      int j;
  
      for (i=size; i&gt;0; i=i/2){
          for (j=0; j&lt;i; j++){
              Merge(data + j*size/i, size/i);
          }
      }
  }
  </code></pre>
  
  <p>which apparently works for sequences of size $2^n$. However, when I run it in sequences of size different than $2^n$, it does not sort right, so in some point of <code>MergeSort_NonRecursive</code>, my code I must be mistaken.</p>
  
  <p>So where did I do wrong (in <code>MergeSort_NonRecursive</code>)? (also, I need to use the <code>Merge</code> funcion).</p>
  
  <p>Thanks in advance.</p>