### Merge and Mergesort

Algorithm代做 | java | 代写project | assignment代做 – 这是一个Algorithm设计的practice, 考察对排序等Algorithm的理解, 包括了Algorithm/java等方面, 使用的程序语言是python

This programming assignment is about Merge and Mergesort. It has two parts. The first part is to produce an input for Mergesort where during Merge the values in the two lists always interleave, and then generalize this to blocks of contiguous values, where the blocks always interleave. The second part is to investigate the average case of Merge and Mergesort, and then generalize this to blocks of contiguous values. For this assignment Merge and Mergesort always refer to the versions on our website (inside the document Sorting algorithms). Do NOT use the merge Algorithm from our book.

#### MERGESORT WITH INTERLEAVED MERGES

This part has two subparts. The first subpart is really only here for clarity. You do not have program it separately from the second subpart.

Standard Version

Write a program that inputsn, and produces a list of thenvalues 1, 2, 3, 4,.. .,n, so that, when Mergesort is run on the list, every merge interleaves the values, and the smallest value always comes from the first list. Youmustdo this with a recursive algorithm that essentially reverse engineers Mergesort.

Example: Ifn= 4 the output should be:

```
1 , 3 , 2 , 4
```

If MergeSort is run on this list, the lists (1) and (3) are merged giving (1,3), then the lists (2) and (4) are merged giving (2,4), and, finally, the lists (1,3) and (2,4) are merged giving (1,2,3,4). Observe that when merging (1, 3) and (2, 4), we create merged list (1, 2, 3, 4) by alternating between the two lists.

Example: Ifn= 5 the output should be:

```
1 , 5 , 3 , 2 , 4
```

If MergeSort is run on this list, the lists (1) and (5) are merged giving (1,5), then the lists (1,5) and (3) are merged giving (1,3,5), then the lists (2) and (4) are merged giving (2,4), and, finally, the lists (1,3,5) and (2,4) are merged giving (1,2,3,4,5).

Example: Ifn= 11 the output should be:

```
1 , 9 , 5 , 3 , 11 , 7 , 2 , 10 , 6 , 4 , 8
```

Generalization to Blocks

Extend your program to include a second parametersso that, for every merge, the interleaving is by blocks of sizesof contiguous values. So the firstsvalues come from the left side, the second svalues come from the right side, the nextsvalues come from the left side, the nextsvalues come from the right side, etc. The last two blocks may each have fewer thansvalues. (Note that the left side can have at most one more value than the right side, so the last block from the left side can have at most one more value than the last block from the right side. There is a special case of the left side having a block with one element and then there is no block from the right side.) You mustdo this with a recursive algorithm that essentially reverse engineers Mergesort.

Example: Ifn= 4 ands= 2 the output should be:

```
1 , 2 , 3 , 4
```

Example: Ifn= 5 ands= 2 the output should be:

```
1 , 2 , 5 , 3 , 4
```

Example: Ifn= 8 ands= 2 the output should be:

```
1 , 2 , 5 , 6 , 3 , 4 , 7 , 8
```

Example: Ifn= 13 ands= 3 the output should be:

```
1 , 2 , 3 , 13 , 7 , 8 , 9 , 4 , 5 , 6 , 10 , 11 , 12
```

Example: Ifn= 21 ands= 4 the output should be:

```
1 , 2 , 3 , 4 , 17 , 18 , 9 , 10 , 11 , 12 , 19 , 5 , 6 , 7 , 8 , 20 , 13 , 14 , 15 , 16 , 21
```

```
We flesh out the top level of MergeSort on this list. Here is the list cut in half:
```

#### 1 , 2 , 3 , 4 , 17 , 18 , 9 , 10 , 11 , 12 , 19

#### ^5 ,^6 ,^7 ,^8 ,^20 ,^13 ,^14 ,^15 ,^16 ,^21

```
Here is what the left and right halves look like after sorting the left and right halves:
```

#### 1 , 2 , 3 , 4 , 9 , 10 , 11 , 12 , 17 , 18 , 19

#### ^5 ,^6 ,^7 ,^8 ,^13 ,^14 ,^15 ,^16 ,^20 ,^21

```
Here are the blocks on the left and right halves before the final merge:
```

#### [1, 2 , 3 , 4], [9, 10 , 11 ,12], [17, 18 , 19]

#### [5, 6 , 7 ,8],[13, 14 , 15 ,16], [20,21]

Example: Ifn= 25 ands= 6 the output should be:

```
1 , 2 , 3 , 4 , 5 , 6 , 25 , 13 , 14 , 15 , 16 , 17 , 18 , 7 , 8 , 9 , 10 , 11 , 12 , 19 , 20 , 21 , 22 , 23 , 24
```

#### EXPERIMENTS

We would like to experimentally estimate the average number of COMPARISONS for Merge and Mergesort. Exactly how to do the experiments is up to you. If you are not sure what data to collect or how to present it, imagine that the government is interested in your results. You will be called up in front of a congressional committee and mercilessly grilled while the whole country is watching.

Average Case for Merge

We want to experimently determine how many comparisons Merge does on average to merge two sorted lists each of sizen. For this part, you will need to do experiments with a variety of sizes of n. You will need to create random lists of 2ndistinct values, which might as well be the numbers from 1 to 2n(since only their relative values matter). For each experiment, create a random permutation of the 2nnumbers, such that the first and second halves are each sorted. You must write the permutation code yourself, i.e. do not use a library routine; you may use the random number generator provided. Note: For the submit server to run correctly on the test cases you must use the numbers 1 to 2n, not 0 to 2n1.

LetM(n) be the average number of comparisons. We know that the worst case is 2n 1 comparisons. We expectM(n) to be close to 2n1, so we expectM(n) = 2n 1 M(n) to grow very slowly. This means that we may be able to estimate its behavior.

- Make a table withn,M(n),M(n).
- GraphnversusM(n).
- GraphnversusM(n).
- Give a formula that estimatesM(n).
- Give a formula that estimatesM(n).

It turns out that the average number of comparisons for Merge is^2 n 2 n+1^2 n2. SoM

```
(n) should
```

converge to 1. The intention is to do the experiments as if you do not know this formula, and only use the formula to make sure that your results make sense.

Average Case for Mergesort

We want to experimently determine how many COMPARISONS Mergesort does on average. For this part, you will need to do experiments with a variety of sizes ofn(without restriction on their values). You will need to create random lists ofndistinct values, which might as well be the numbers from 1 ton(since only their relative values matter). For each experiment, create a random permutation of thennumbers. (Note: For the submit server tests to run correctly, you must use the numbers 1 ton, not 0 ton1.)

LetS(n) be the average number of comparisons. We expect that the average case number of comparisons to beS(n) =nlgn+O(n), where the linear term might be negative, so we expect S(n) = (S(n)nlgn)/nto look like a constant asymptotically. This means that we may be able to estimate the constant.

- Make a table withn,S(n),S(n).
- GraphnversusS(n).
- GraphnversusS(n).
- Give a formula that estimatesS(n). What can you say aboutS(n)?
- Give a formula that estimatesS(n). What can you say aboutS(n)?

Average Case for Mergesort with blocks

We would like to see how Mergesort performs with blocks ofscontiguous, sorted values (for some constants). For example ifn= 15 ands= 3 then a list might look like:

```
7, 8, 9, 1, 2, 3, 10, 11, 12, 13, 14, 15, 4, 5, 6
```

LetS(s, n) be the average number of comparisons for blocks of sizes. We expectS(s, n) = (S(s, n)nlgn)/nto look like a, possibly negative, function ofs. This means that we may be able to estimate its behavior. We want to concentrate on the behavior ofS(s, n) as a function of the block size. We will graphsversusS(s, n) fornlarge: For each value ofsthat you are graphing, fixnat some large multiple ofs, and do some random experiments to get the average. What can you say about S(s, n)? What can you say aboutS(s, n)?

#### PROGRAMMING RULES

You must write these programs yourself. You may discuss general ideas with other people. You may not look at any othercodeorpseudo-code(even if it is on the internet), other than what is on our website or in our book.

#### SUBMISSION GUIDELINES

You will implement programs for both parts in java and submit it on Gradescope. A skele- ton code is provided on the course website and you must build you own program upon it. To start, if you use Eclipse, you can create a new project and copy the foldercmsc351f19into src under your project folder. If you use commandline tools, you can compile the code by javac cmsc351s19/*.javaand execute Main byjava cmsc351f19.Main. You should not change the name of MergeSorter.javaorPermutationGenerator.java. You can, however, create new classes and new JAVA files as you see appropriate. When creating new classes, make sure all of them lie in the same packagecmsc351f19by addingpackage cmsc351f19at the top of each file. Moreover, you should not change the name and signature of methods that are already in the skeleton code, but you can create your own helper functions and class members. To help you test your code, weve included aMain.javato read space-separated integers that set different parame- ters inMergeSorter.java. When you implementPermutationGenerator.java, you should use mrandomdefined in the constructor as your source of randomness. After you finish, pack all your .java files in a zip archive and submit it under MergeSort – Code. After you submit the code, make sure that your code compiles by checking the autograder output on Gradescope. In addition, submit a pdf file containing experiment results from PART 2 under MergeSort – Writeup.