simple mergesort

Even though I've studied this algorithm a couple of times, I've never had to implement it before. So I assigned it to myself.

/** should have a time-complecity of O(N×log(N))
    and a space-compelcity of O(N) **/
void mergesort(int N, int array[]) {
  int k; // k is the block size.
  int x; //x is which block we are at.
  int i,j; //indices in old[]
  int p; // index in new[]
  int ilimit,jlimit; //end of blocks.
  int *hold = malloc(sizeof(hold) * N);
  if (hold == NULL) {
    fprintf(stderr,"malloc failed\n");
    exit(2);
  }
  int *new = hold;
  int *old = array;
  int *tmp;
  for (k = 1; k < N; k *= 2) {
    p = 0;
    for (x = 0; x < N; x += (2*k)) {
      i = x;
      ilimit = i + k;
      j = ilimit;
      if (ilimit >= N) {
	while (i < N)
	  new[p++] = old[i++];
 	break; //out of for-loop
      }
      jlimit = j + k;
      if (jlimit >= N)
	jlimit = N;
      while (1) {
	if (old[i] < old[j]) {
	  new[p++] = old[i++];
	  if (i == ilimit) {
	    while (j < jlimit)
	      new[p++] = old[j++];
	    break; //out of while-loop
	  }
	} else {
	  new[p++] = old[j++];
	  if (j == jlimit) {
	    while (i < ilimit)
	      new[p++] = old[i++];
	    break; //out of while-loop
	  }
	}
      } // End while loop.
    } // End inner for loop.
    tmp = old; old = new; new = tmp;
  }// End outer for loop.
  if (old != array)
    for (i = 0; i < N; i++)
      array[i] = old[i];
  free(hold);
  return;
}

Next step is to translate to Java and use .compareTo() with arrays of references:

  public static void mergeSort(Comparable array[]) {
    int N = array.length;
    int k; // k is the block size.
    int x; // x is which block we are at.
    int i,j; //indices in old[]
    int p; // index in new[]
    int ilimit,jlimit; // end of blocks.
    Comparable hold [] = new Comparable [N];
    Comparable neww [] = hold;
    Comparable old [] = array;
    Comparable tmp [];
    for (k = 1; k < N; k *= 2) {
      p = 0;
      for (x = 0; x < N; x += (2*k)) {
        i = x;
        ilimit = i + k;
        j = ilimit;
        if (ilimit >= N) {
          while (i < N)
            neww[p++] = old[i++];
          break; //out of for-loop
        }
        jlimit = j + k;
        if (jlimit >= N)
          jlimit = N;
        while (true) {
          if (old[i].compareTo(old[j]) < 0) {
            neww[p++] = old[i++];
            if (i == ilimit) {
              while (j < jlimit)
                neww[p++] = old[j++];
              break; //out of while-loop
            }
          } else {
            neww[p++] = old[j++];
            if (j == jlimit) {
              while (i < ilimit)
                neww[p++] = old[i++];
              break; //out of while-loop
            }
          }
        } // End while loop.
      } // End inner for loop.
      tmp = old; old = neww; neww = tmp;
    }// End outer for loop.
    if (old != array)
      for (i = 0; i < N; i++)
        array[i] = old[i];
  }