[原]Touch on Merge Sort

The famous "divide-and-conquer" principle says, divide the problem to similar smaller one, then resolve it recursively. RECURSION is another topic which is very complex. I am wondering how smart the guy is to develop recursion.

OK, let's check how we can divide the sort: To sort a list (here array is used), we break the array into two parts, sort them separately, then merge the result. The two parts themselves can be sorted use the same method. So here comes the MergeSort algorithm:

if the array is not sorted (this will be false if the array contains only 1 element)
then divide the array to 2 parts with each size set to array.length/2
    MergeSort the 1st array;
    MergeSort the 2nd array;
    Merge the 2 arrays.

Now the translation is easy:

void MergeSort(int* aArray, int aStart, int aEnd)
{
    int aMid = 0;
    // The array is not sorted
    if (aEnd > aStart)
    {
        // Divide the array to 2 parts.
        aMid = (aStart + aEnd) / 2;
        // Sort 1st array
        MergeSort(aArray, aStart, aMid);
        // Sort 2nd array
        MergeSort(aArray, aMid + 1, aEnd);
        // Merge the result
        Merge(aArray, aStart, aMid, aEnd);
    }
}

We need Merge() to merge the 2 arrays:

for all elements in 2 arrays
    select the smallest one and insert to result
copy the remaining elements of 2 arrays to result, if any.

Someone prefers to use sentinel to do this, but it's not so flexible. So we use this:

// Merge() merges 2 subarrays of aArray into sorted ordered array and store back
// to aArray. The 1st starts from aStart and ends with aMid, the 2nd starts with
// aMid + 1 and ends with aEnd.
void Merge(int* aArray, int aStart, int aMid, int aEnd)
{
    // Get a temporary storage to store the result
    int resultlen = aEnd - aStart + 1;
    int* temp = new int[resultlen];
    int begin1 = aStart;
    int end1 = aMid;
    int begin2 = aMid + 1;
    int end2 = aEnd;
    int index = 0;
    // Copy the smallest of the 2 sorted array to temp
    while (begin1 <= aMid && begin2 <= aEnd)
    {
        if (aArray[begin1] <= aArray[begin2])
            temp[index++] = aArray[begin1++];
        else
            temp[index++] = aArray[begin2++];
    }
    // Copy the remaining array to temp
    while (begin1 <= aMid)
        temp[index++] = aArray[begin1++];
    while (begin2 <= aEnd)
        temp[index++] = aArray[begin2++];
    // Copy the result to aArray
    CopyInt(aArray + aStart, temp, resultlen);
    // Free the temporary storage
    delete [] temp;
}