Merge Sort in C with O(N*log[N]) Runtime

For开发者_如何学C an assignment, we are to write the merge sort function in C:

sort(int* array, unsigned len);

I have the code written and working, but its runtime is O(N^2*log[N]) which defeats the purpose of merge sort. The reason for the inefficiency is because the merge part is as follows:

while(ct1 < len1 && ct2 < len2){
    if(array[0] < array[len1 - ct1]){
        ct1++;
        array++;    // no longer look at that element
    }
    else{
        int position = len1 - ct1;
        int hold = array[position];
        while(position > 0){
            array[position] = array[position - 1];
            position--;
        }
        array[0] = hold;
        ct2++;
        array++;
    }
}

where ct1 is a counter for the left list, ct2 is counter for the right list, and array is the pointer to the array. Both ct1 and ct2 are initially set to zero. Like I said, this works, it's just inefficient because you have to shift everything. I was wanting to split the sub arrays into two temporary arrays before sorting, but you supposedly cannot create arrays whose lengths aren't defined as constants. I should also note that although I can use helper functions, I cannot change the function parameters: there must be a pointer to an array, and the length.

You can create arrays that are not constant length, google malloc. Merge sort requires use of auxiliary memory to work right. You must free memory allocated by malloc when you are done with it.