Why is my mergesort not working?

Question

Algorithms

Hello.
I decided to learn algorithms and write them in pure C, because I know C a little, but I also want to improve it. I decided to start by writing algorithms.
For several days I have been trying to merge sort, doing it according to the pseudocode described in Introduction to Algorithms.

void
merge(int *array, int start, int mid, int end)
{ 

  int leftLen = mid - start,
      rightLen = end - mid,
      left[leftLen], right[rightLen],
      i, j, k;

  for (i = 0; i < leftLen; i++) {
    left[i] = array[start+i];
  }

  for (j = 0; j < rightLen; j++) {
    right[j] = array[mid+j];
  }

  i = 0;
  j = 0;
  
  for (k = start; k < end; k++) {
    if ((i < leftLen && left[i] < right[j]) || j >= rightLen) {
      array[k] = left[i];
      i++;
    } else {
      array[k] = right[j];
      j++;
    }
  }
}


void mergeSort(int *array, int start, int end)
{
  int mid = (start + end) / 2;
  if (start < end) {
    mergeSort(array, start, mid);
    mergeSort(array, mid+1, end);
    merge(array, start, mid, end);
  }
}


int
main(int argc, const char *argv[])
{
  int array[] = {3,2,6,4,1,8,7,9,5},
      arrayLen = sizeof(array)/sizeof(int);

  mergeSort(array, 0, arrayLen);
}

I would be grateful for help.

Answer 1

Two errors are visible. The first one should not affect the result, but may cause the index to go beyond the array boundary:
In the case when j==rightLen, you will check the right[j] element. The conditions here need to be reversed:
The second is that the element array[mid] will not participate in either the first or the second recursive calls to mergeSort. The second call had to be made
And in order to avoid infinite recursion, change the condition in mergeSort to
(or to if(start < mid) ).
Well, in classical C, the construction

int leftLen = mid - start,
      left[leftLen];

There, arrays can only be of fixed length, and for dynamic capture, you have to use malloc. But if it compiles, then your compiler version allows it.
UPD. Variable length arrays are indeed possible in C99, and gcc is said to support them. Well, okay. Visual Studio does not allow this.

Answer 2

int left[leftLen]
Be careful, on "combat" tasks it is fraught with a stack overflow. The call stack is small, just a few megabytes.