In this lab you are asked to implement two versions of merge sort on linked lists: one that produces a new, sorted list and another that works in-place by changing the input list.
Section 7.6 of the textbook describes merge sort on an array (lecture notes). You’ll need to adapt the algorithm for linked lists. The steps of the algorithms are
The main difference between the two versions that you are supposed to write is that the sorted list is new in the first, functional version, while it overwrites the input list in the second, in-place version. We will explain the difference using examples:
[Example 1] The sort function applied to the following linked list
[5] -> [2] -> [7] -> [1]
produces the following new linked list, while leaving the original one unchanged:
[1] -> [2] -> [5] -> [7]
[Example 2] The sort_in_place() function applied to the following list
[6] -> [3] -> [8] -> [2]
should rearrange the nodes into the following order:
[2] -> [3] -> [6] -> [8]
Utils.java helpful.MergeSort.java (Problem 1)
and lab write-up README.md (Problem 3) to
link.MergeSortTest.java (Problem 2) to
link.Prerequisite: download student support code and import the project into IntelliJ.
Look at MergeSort.java in the student support code. Apart from sort() and sort_in_place(),
it also contains type signatures for merge() and merge_in_place(). The sort functions call
their respective merge functions to combine two sorted halves into one. Similar to their sorting
counterparts, merge() creates a new list from two input lists while merge_in_place() works
in-place by rearranging the nodes.
[Example 3] The merge() function applied to the following two sorted lists
[1] -> [2] -> [5] -> [7]
[2] -> [3] -> [6] -> [8]
produces the following newly allocated list
[1] -> [2] -> [2] -> [3] -> [5] -> [6] -> [7] -> [8]
Implement both sort() (functional) and sort_in_place() (in-place) in class MergeSort.
Both sort functions have a Node-typed parameter and Node return type, which point to
the first node in the input list and the first node in the output list.
The Node class is defined in Node.java.
The two sort functions should call their respective merge functions, merge() and
merge_in_place(), so you are supposed to implement those merge functions as well.
Before running your code on Autograder, create your own test cases and run them locally.
Think about their correctness criteria of the two versions of merge sort.
Write regular, corner, and random test cases for merge(), sort(), merge_in_place(),
and sort_in_place().
merge() and sort() create new output listssort() and sort_in_place() are sortedsort() and sort_in_place() are permutations
of their input listsRun your test cases on Autograder against four buggy implementations and see whether they can catch all the bugs!
Answer the following questions in your lab write-up (README.md):
merge() function?sort() function?merge_in_place() function?sort_in_place() function?Make sure MergeSort.java, MergeSortTest.java and README.md were submitted.