## CSE 131 Module 6: Recursion

Important!

Before beginning any work, do a Team...Pull in your repository.

### Procedure

Update your repository so that you see a lab6 package in the labs source folder.

#### Merge Sort

1. Watch this video on merge sort:
2. Implement createMergeCombinedArray
3. ```/**
* Creates a new array whose contents are a sorted in ascending lexicographical
* order version of the subrange [min, maxExclusive) in the specified array.
*
* For example, the array: { "H", "S", "C", "M", "I", "P" } with min: 1 and
* maxExclusive: 3 would process the indices [1,3) (that is: 1 and 2) to return
* a new array: { "C", "S" }.
*
* This method must not mutate (that is: change the contents of) the specified
* array, nor would it have any real reason to do so.
*
* @param array
*            an array
* @param min
*            the minimum index of interest (inclusive)
* @param maxExclusive
*            the maximum index of interest (exclusive)
* @return a sorted array of the subrange of contents in the specified array
*         from [min, maxExclusive).
*/
private static String[] createSortedArrayInRange(String[] array, int min, int maxExclusive) {
throw new NotYetImplementedException("delete this line of code and implement this method.");
}
```
4. Run the MergeSortTestSuite in the lab6.tests package to test your work.
Note: MergeSortDemonstrationVideoCompanionTest may be useful for debugging as it matches the above video.
5. Compare your implementation of Merge Sort against your implementation of Selection Sort with the SortPerformanceTimingChartApp in the lab6.chart package to test your work.

#### Triangle

1. Consider the picture below.

• Think about what you see: what is foreground and what is background?
• Develop an approach for drawing the figure recursively.
• What is the base case?
• What are the recursive calls doing?
• Create a Triangles class in the lab6 package.
• Implement your ideas in the Triangles class, and be prepared to demo and discuss your code to a TA to receive credit for this lab.

• You must commit and push all of your work to your repository. It's best to do this from the top-most level of your repository, which bears your name and student ID.
• You must demo the commited work to a TA. Make sure the TA knows that your demo is for credit at this point.
• Follow the directions below to have your demo for this work recorded.

When you are done with this lab, you must be cleared by the TA to receive credit.
• Do a Team…Pull to update your repository. You must do this or the commit/push below may fail.
Make certain this has worked by logging into bitbucket. There you will see the commit(s) in your news feed if it was successful. You can also check the Source page to locate and ensure your code was received.

It is your responsibility to make certain the code has been pushed. Some of your work receives credit through testing of your pushed code. You will receive no credit for such work if you failed to push. We generally reserve the right to revoke credit for any of your work that has not been pushed on-time.

• Fill in the form below with the relevant information
• Have a TA check your work
• The TA should check your work and then fill in the TA's name
• Click OK while the TA watches
• If you request propagation, it does not happen immediately, but should be posted in the next day or so

This demo box is for lab 6
 Credit (TA, verify!): ½ credit Merge sort works, but not Sierpinski ½ credit Sierpinski works, but not Merge sort Full credit Both Merge sort and Sierpinski work
 Last name WUSTL Key Propagate? (NOT your numeric ID) Do not propagate lower case only e.g. Smith j.smith 1

Acknowledgements and assertion of integrity