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

Implement the GetSortedRunLength$()$ member function in NaturalMergeSorter.h$.$ Access NaturalMergeSorter.h by clicking on the orange arrow next to main.cpp at the top of the coding window.

GetSortedRunLength$()$ has three parameters:

array: a pointer to an array of integers,

arrayLength: an integer for the array's length, and

startIndex: an integer for the run's starting index.

The function returns 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. The function returns $0$ if startIndex is out of bounds.

File main.cpp has several test cases for GetSortedRunLength$()$ that can be run by clicking the "Run program" 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 length

If 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$

NaturalMergeSorter.h: #ifndef NATURALMERGESORTER$\_$H

#define NATURALMERGESORTER$\_$H

class NaturalMergeSorter $\{$

public:

virtual int GetSortedRunLength$($int$*$ array, int arrayLength, int startIndex$)\{$

$//$ Your code here

$\}$

virtual void NaturalMergeSort$($int$*$ array, int arrayLength$)\{$

$//$ Your code here

$\}$

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$]$;

leftPos$++$;

mergePos$++$;

$\}$

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

while $($rightPos $<=$ rightLast$)\{$

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

rightPos$++$;

mergePos$++$;

$\}$

$//$ Copy merged numbers back to numbers

for $($mergePos $=0$; mergePos $<$ mergedSize; mergePos$++)\{$

numbers$[$leftFirst $+$ mergePos$]=$ mergedNumbers$[$mergePos$]$;

$\}$

$//$ Free temporary array

delete$[]$ mergedNumbers;

$\}$

$\}$;

#endif