Sequential Merge Sort in C

Question

I am trying to re-write a recursive Merge Sort like

void MergeSort(int* data, int size){
  int half=size/2;
  if (size > 1) {
    MergeSort(data, half);
    MergeSort(data+half, half);
    Merge(data, size);
  }
}

in which

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<size; cnt++){
    if (cntLow == half) 
      sorted[cnt] = data[cntHigh++];
    else if (cntHigh == size)
      sorted[cnt] = data[cntLow++];
    else if (data[cntLow] <= data[cntHigh])
      sorted[cnt] = data[cntLow++];
    else
      sorted[cnt] = data[cntHigh++];
  }

  for (cnt=0; cnt<size; cnt++)
    data[cnt] = sorted[cnt];

  free(sorted);
}

to a non-recursive call. So I wrote the function

void MergeSort_NonRecursive(int* data, int size){
    int i;
    int j;

    for (i=size; i>0; i=i/2){
        for (j=0; j<i; j++){
            Merge(data + j*size/i, size/i);
        }
    }
}

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 MergeSort_NonRecursive, my code I must be mistaken.

So where did I do wrong (in MergeSort_NonRecursive)? (also, I need to use the Merge funcion).

Thanks in advance.

Answer 1

Since size is an int, size/2 truncates your quotient.

e.g. if size=4, size/2 = 2. if size=5, size/2 = 2. if size=6, size/2 = 3.

So for a size of 5, you want the first MergeSort recursive call to operator on size/2 elements (i.e. the first 3), and the second call to operate on the remaining 2 elements.

You can say e.g.

int half = size/2; //size = 5: half = 2
int rest = size - half; //rest = 3

so:

void MergeSort(int* data, int size){
  int half=size/2;
  int rest = size-half;
  if (size > 1) {
    MergeSort(data, half);
    MergeSort(data+half, rest); //changed this line
    Merge(data, size);
  }
}

Edit:

Looks like you changed the question slightly, after I posted. The general idea still stands: When you divide an int by another int, the quotient is truncated.

In your MergeSort_NonRecursive, you're dividing ints in a number of places, e.g. i=i/2, j*size/i, size/i. Pay attention to the values that you would get.