Rewrite this merge sort algorithm into a recursive one without creating a temporary array

#include

#include

using namespace std;

#include "ArrayUtilities.cpp"

void MergeSort(int A[], int LO, int HI)

{

int mid = (LO + HI) / 2;

if (LO >= HI) return;

MergeSort(A,LO,mid);

MergeSort(A,mid+1,HI);

Merge(A, HI+1, LO, mid, mid+1, HI);

}

//ArrayUtilities.cpp

void Merge(int A[], int Asize, int lLO, int lHI, int rLO, int rHI)

{

int Temp[Asize+1]; // Temp array to hold the merge.

int tnext = lLO; // Cursor for temp array, filled left to right.

int left = lLO, right = rLO;

while (left<=lHI && right <= rHI)

{

if (A[left] <= A[right])

{

Temp[tnext++] = A[left++];

}

else

{

Temp[tnext++] = A[right++];

}

}

//-| Copy remaining elements from A[lLO:lHI] (A[rLO:rHI]).

while (left <= lHI)

{

Temp[tnext++] = A[left++];

}

while (right <= rHI)

{

Temp[tnext++] = A[right++];

}

//-| Copy the Temp sub-array back into array A[lLO:rHI].

for (int k=lLO; k<=rHI; k++)

{

A[k] = Temp[k];

}

}