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. 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.MergeSortTest.java (Problem 1) to
link.MergeSort.java (Problem 2)
and lab write-up README.md (Problem 3) to
link.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]
Before implementing the two versions of merge sort, think about their correctness criteria.
Write regular, corner, and random test cases for merge(), sort(), merge_in_place(),
and sort_in_place().
Run your test cases on Autograder against four buggy implementations and see whether they can catch all the bugs!
merge() and sort() create new output listssort() and sort_in_place() are sortedsort() and sort_in_place() are permutations
of their input listsImplement both sort() (functional) and sort_in_place() (in-place) in class MergeSort.
Both 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 respectively.
As is mentioned in Problem 1, they should call merge() and
merge_in_place() respectively, which you are supposed to implement as well.
The Node class is defined in Node.java.
Before running your code on Autograder, test locally using your own test cases from Problem 1.
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.