Please help me code this in C$++$ for my data structures course:

Natural merge sort overview

The merge sort algorithm recursively divides the array in half until an array with one element is reached. A variant of merge sort, called natural merge sort, instead finds already$-$sorted runs of elements and merges the runs together.

Ex: The unsorted array below has five sorted runs.

Natural merge sort starts at index $0$ and finds sorted runs A and B $.$ Runs A and B are merged, using the same merging algorithm asnmerge sort, to make run F$.$

Next, the algorithm starts after the merged part F$,$ again looking for two sequential, sorted runs. Runs C and D are found and merged to

make run G$.$

The algorithm then starts after the merged portion G $.$ Only one run exists, run E $,$ until the end of the array is reached. So the algorithm

starts back at index $0,$ finds runs F and G$,$ and merges to make run H$.$

Again, a single run is found after the just$-$merged part, so the search starts back at index $0.$ Runs H and E are found and merged.

One last search for a sorted run occurs, finding a sorted run length equal to the array's length. So the array is sorted and the algorithm terminates.

Step $1$: Implement the GetSortedRunLength$()$ member function

Implement the GetSortedRunLength$()$ member function in NaturalMergeSorter.h$.$ GetSortedRunLength$()$ has three parameters:

array: A pointer to an array of integers

arrayLength: An integer for the array's length

startIndex: An integer for the run's starting index

Return the number of array elements sorted in ascending order, starting at startIndex and ending either at the end of the sorted run, or the end of the array, whichever comes first. Return $0$ if startIndex is out of bounds.

File main.cpp has several test cases for GetSortedRunLength$()$ that can be run by clicking the$$Run button. One test case also exists for NaturalMergeSort$(),$ but that can be ignored until step two is completed.

The program's output does not affect grading.

Submit for grading to ensure that the GetSortedRunLength$()$ unit tests pass before proceeding.

Step $2$: Implement the NaturalMergeSort$()$ member function

Implement the NaturalMergeSort$()$ member function in NaturalMergeSorter.h$.$ NaturalMergeSort$()$ must:

Start at index$$i $=0$

Get the length of the first sorted run, starting at$$i

Return if the first run's length equals the array lengthIf the first run ends at the array's end, reassign$$i $=0$ and repeat step $2$

Get the length of the second sorted run, starting immediately after the first

Merge the two runs with the provided Merge$()$ function

Reassign$$i with the first index after the second run, or $0$ if the second run ends at the array's end

Go to step $2$ Step $1$: Implement the GetSortedRunLength$()$ member function

Implement the GetSortedRunLength$()$ member function in NaturalMergeSorter.h$.$ GetSortedRunLength$()$ has three parameters:

$-$ array: A pointer to an array of integers

$-$ arrayLength: An integer for the array's length

$-$ startIndex: An integer for the run's starting index

Return the number of array elements sorted in ascending order, starting at startIndex and ending either at the end of the sorted run, or the end of the array, whichever comes first. Return $0$ if startIndex is out of bounds.

File main.cpp has several test cases for GetSortedRunLength$()$ that can be run by clicking the Run button. One test case also exists for NaturalMergeSort$(),$ but that can be ignored until step two is completed.

The program's output does not affect grading.

Submit for grading to ensure that the GetSortedRunLength$()$ unit tests pass before proceeding.

Step $2$: Implement the NaturalMergeSort$()$ member function

Implement the NaturalMergeSort$()$ member function in NaturalMergeSorter.h$.$ NaturalMergeSort$()$ must:

$1.$ Start at index $\backslash ($ i$=0\backslash )$

$2.$ Get the length of the first sorted run, starting at i

$-$ Return if the first run's length equals the array length

$-$ If the first run ends at the array's end, reassign i $=0$ and repeat step $2$

$3.$ Get the length of the second sorted run, starting immediately after the first

$4.$ Merge the two runs with the provided Merge$()$ function

$5.$ Reassign i with the first index after the second run, or $0$ if the second run ends at the array's end

$6.$ Go to step $2$

$$ Files main.cpp

C$.$ NaturalMergeSorter.h

RunLengthTestCase.h

Run

$(5)$ History

$```$

virtual void Merge$($int$*$ numbers, int leftFirst, int leftLast,

int rightLast$)\{$

int mergedSize $=$ rightLast $-$ leftFirst $+1$;

int$*$ mergedNumbers $=$ new int$[$mergedSize$]$;

int mergePos $=0$;

int leftPos $=$ leftFirst;

int rightPos $=$ leftLast $+1$;

$//$ Add smallest element from left or right partition to merged numbers

while $($leftPos leftLast && rightPos rightLast$)\{$

if $($numbers$[$leftPos numbers$[$rightPos$])\{$

mergedNumbers$[$mergePos$]=$ numbers$[$leftPos$]$;

leftPos$++$;

$\}$

else $\{$

mergedNumbers$[$mergePos$]=$ numbers$[$rightPos$]$;

rightPos$++$;

$\}$

mergePos$++$;

$\}$

$//$ If left partition isn't empty, add remaining elements to mergedNumbers

while $($leftPos leftLast$)\{$

mergedNumbers$[$mergePos$]=$ numbers$[$leftPos$]$;

$```$

$```$

$//$ If left partition isn't empty, add remaining elements to mergedNumbers

while $($leftPos leftL