Merge-sort

Mergesort Learning objectives: Show understanding of mergesort, a commonly used sorting algorithm Write code that correctly manipulates linked lists Analyze the complexity of a modification to the mergesort algorithm (This is adapted from exercise 2.2.16 on p. 285 of the textbook.) Implement a natural mergesort for linked lists. (This is the method of choice for sorting linked lists because it uses no extra space and is guaranteed to be linearithmic.) Write a version of bottom-up mergesort (pages 277-279 of the textbook) for linked lists (not arrays) that takes advantage of order in the list by proceeding as follows each time it needs to find two lists to merge: Find a sorted sublist (by following links in the list until finding an entry that is smaller than its predecessor in the list), then find the next, then merge them. Include unit tests that show how you verified that your program works (expected input/output). Your unit tests should be in the main() method. See p. 26 of the textbook. Tests must be automated. None of your programs should accept any input from the user. In your lab report, analyze the running time of this algorithm in terms of the list length and the number of maximal increasing subsequences in the list. A maximal increasing subsequence of an list l is: Supposing start >= 0 and end < l.length(), A sublist of l starting from the startth position and ending with the endth position such that for any start <= i < end -1, the ith element of the list is less than or equal to the (i + 1)th element of the list that's as long as possible. For example, if l = [9, 1, 2, 5, 10, 3] then: [1, 2, 5, 10] is a maximal increasing subsequence because: 1 <= 2, 2 <= 5, 5 <= 10 and we cannot create a longer increasing subsequence by adding other list elements on the front or back [2, 5] is not a maximal increasing subsequence because a longer increasing subsequence, [1, 2, 5, 10], includes it. Getting started: In Eclipse: Right-click on the "Lab2" icon in the left sidebar. Select "Build Path" from the pop-up menu, then select "Add Libraries..." from the second menu that pops up. Make sure "JRE System Library" is selected (highlighted). Click Next. Click Finish. Right-click on the "Part1" folder underneath the "Lab2" icon. In the menu that pops up, select "Build Path", then select "Use as source folder" from the second menu that pops up. To run the code, right-click on the "Mergesort.java" icon in the sidebar and select "Run As", then "Java application" from the second menu that pops up. You can also go to the Run menu > "Run As" > "Java application". You will see a NullPointerException, which is expected; start editing the code so that the tests will pass! Alternately, or if you're not using Eclipse: https://github.com/catamorphism/cis27/tree/master/Lab2/Part1 (Links to an external site.) and copy/paste the three Java files there into your project.