Recursive Merge Sort Without Arrays

Question

This is a problem I'm working on right now without any idea how to solve. I'm supposed to write the pseudocode to the merge function, but I'm not sure what I'm supposed to do. What I've been given is as follows:

Begin MergeSort(L[], start, stop)
   if (stop<=start) return;
   int m = (start+stop)/2;
   MergeSort(L, start, m);
   Mergesort(L, m+1, stop);
   merge(L, start, m, stop);
End MergeSort

The only other thing I've been told is that I'm supposed to find the "merge(L, start, m, stop);" line. I've been researching all day, and everything I've found says that you should have 2 arrays, called left and right, to assign the recursive lines, making:

Begin MergeSort(L[], start, stop)
   if (stop<=start) return;
   array left[];
   array right[];
   int m = (start+stop)/2;
   left=MergeSort(L, start, m);
   right=Mergesort(L, m+1, stop);
   merge(L, start, m, stop);
End MergeSort

If I were given this problem, I would be able to solve it, but I'm stuck because once I've broken each sublist into single elements, I'm not even sure what I'm supposed to call them, so I'm not sure how to work with them.

I'm still a beginner when it comes to code (taking the very basics of C and Python), so please keep the answer simple, if possible.

Thank you very much for reading this, and I hope that I get an answer so I understand what I'm doing.

Answer 1

MergeSort consists of 2 functions: mergeSort and merge. First one you have already written correctly. So, the only you problem with merge function. Because of merge sort is not in-space sort algorithm, it require extra space to store data. Bellow is pretty simplified version of merge function that creates extra array of size stop - start:

Begin merge(L[] array, int start, int m, int stop) 
    if (start == stop) {
        return;
    }
    int leftPos = start;
    int rightPos = m + 1;

    int curPos = start;

    L[] temp = new L[stop - start];

    while(leftPos <= m && rightPos <= stop) {
        if (array[leftPos] <= array[rightPos]) {
            temp[curPos++] = array[leftPos++];
        } else {
            temp[curPos++] = array[rightPos++];
        }
    }
    while(leftPos <= m) {
        temp[curPos++] = array[leftPos++];
    }
    while(rightPos <= stop) {
        temp[curPos++] = array[rightPos++];
    }

    for (int i = start; i <= stop; i++) {
        array[i] = temp[i - start];
    }
End merge