# Algorithm | java | project作业 | assignment – Merge and Mergesort

### Merge and Mergesort

Algorithm | java | project作业 | assignment – 这道题目是Algorithm相关的编程代写任务, 涉及了Algorithm/java等代写方面, 这是值得参考的assignment代写的题目 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:
``````

#### ^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:
``````

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

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

#### [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.