In this assignment you will implement an in-place Mergesort for singly-linked lists. Merge for singly-linked lists is relatively easy, as it loops through the input in order from beginning to end. However, Mergesort needs to find the middle of the sequence, which would seem to require random-access, something linked lists do not provide. Will this affect the big-O runtime of the algorithm?
/*
* mergesort.cpp
* Mergesort on singly-linked lists.
*/
/* node
The node type for our linked list.
*/
struct node
{
int value;
node* next;
};
// Declarations for the functions below.
node* mergesort(node* input);
node* mergesort(node* input, int length);
node* merge(node* left, node* right);
/* mergesort(input)
Mergesort the list whose head is `input`, returning a new sorted list. This
function should compute the length of the list, and then pass `input` and
the length to the two-parameter recursive `mergesort` overload, below.
Must run in O(n log n) time (but that's because `mergesort(node*,int)`, below
runs in O(n log n)).
Must use O(n) space (i.e., the returned list is created new).
*/
node* mergesort(node* input)
{
// Your code here
}
/* mergesort(input, length)
Recursively Mergesort the `input` list (whose length is given by `length`),
returning a new sorted list.
Must run in O(n log n) time, where n = `length`.
Must use O(n) space (returned list is created new).
NOTE: The `input` list must not be modified in any way.
*/
node* mergesort(node* input, int length)
{
// Your code here
}
/* merge(left, right)
Merge the lists given by `left` and `right`, returning the head of the merged
list (the returned node should either be the head of `left` or the head of
`right`). The two input lists will always be sorted in ascending order.
Must run in O(m+n) time where `m` is the length of `left` and `n` is the
length of `right`.
Must use O(1) space (i.e., this is an in-place operation); no new nodes
may be created.
NOTE: This function should modify the `next` pointers in the nodes, but NOT
modify the `value`s. That is, it merges the lists by updating their list
structure, not by moving values from one list to another.
*/
node* merge(node* left, node* right)
{
// Your code here
}
You can download the above template along with the
test runner source code. On the server,
these can be found in /usr/local/class/src/cs133/.
Requirements
This Mergesort must be in-place (i.e., must use \(O(1)\) memory). This means that your code must not create (or destroy) any
nodes. The test code will create lists to test your functions, and it will destroy them after its done.(In-place Mergesort for arrays is not possible in \(O(n \log n)\) time, but it is possible on linked lists.)
The returned list must be a valid list (no cycles).
The length of the new list must be the same as the length of the input list.
Every value in the input list must occur exactly once in the output list (i.e., the output list is a permutation of the input; this is just one of the requirements for sorting).
For any pair of non-null adjacent
nodes, it must be the case thatn->value ≤ n->next->value(This is the other requirement for sorting.)
Your code must not allocate any dynamic memory other than what is required for the nodes of the returned list. (The test code will destroy this list before exiting, so if run in Valgrind, it should report no memory leaks.)
For
merge(), the returned list must not be new; it must consist only of nodes found already in theleftandrightlists.
Testing
You can download assign3_test.cpp or copy it
from /usr/local/class/src/cs133/assign3_test.cpp on the server.
The test runner will test your
code with arrays of various sizes, making sure that the results contain everything
that the input did.
When you compile, you must ensure that you link with the dl library, as this
is used to track the memory usage of your code. The compile command and the
test-assignment script will handle this automatically for you, but if you
compile with G++ you will need to do it yourself:
g++ -o assign3_test assign3_test.cpp mergesort.cpp -ldl
Submission
Save your work in a directory on the server named cs133/assign3/.
Tests
Tests for list values
These tests are run to check the values in a list, to ensure that it has the values it ought to have.
Incorrect value found in list: expected x but found y
The list was expected to have a value of x, but a different value y was found.
List is too long: expected end-of-list but found rest of list = …
The list is too long: we expected to see the end of the list but there are more values (the check will print the remainder of the list).
List is too short: expected values but found end-of-list.
The list is too short: we expected to see more values, but found the end of the list. (The expected values will be printed as part of the check.)
Tests for merge results
Result of merge()` is not a valid list (contains a cycle?)
After running a merge(), the result list is not even a valid linked list. For
example, it may contain a cycle.
Merged list does not contain all the values it should (ended too early)
As above, the result list of merge is too short: it should contain more values.
Wrong value in merged list: expected x, found y
As above, we expected a value x in a specific position, but we found a different value y.
Invalid node found in merged list (all merged nodes must come from the left/right input lists).
merge is required to merge the lists in place, without creating any new nodes.
The output list contained a node* which did not occur in either of the two
input lists.
Wrong value in merged list: expected x, found y
See above.
Invalid node found in merged list (all merged nodes must come from the left/right input lists).
See above.
Merged list does not contain all the values it should (ended too early)
See above.
Wrong value in merged list: expected x, found y
See above.
Invalid node found in merged list (all merged nodes must come from the left/right input lists).
See above.
Merged list does not contain all the values it should (ended too early)
See above.
Wrong value in merged list: expected x, found y
See above.
Invalid node found in merged list (all merged nodes must come from the left/right input lists).
See above.
Merged list contains more elements than the input left/right lists (extra value(s) = …)
See above.
Tests for merge
Merging two empty lists must return an empty list.
Merging two empty lists must result in an empty result list.
Output list has incorrect node pointers (all output nodes must exist in the input lists).
As above, the result of merge must re-use the pointers from the input lists
(be performed in-place); merge must not create new nodes.
Result is not merged
The results of merge, when given two ascending input lists, must be a
correctly-merged ascending output list.
Tests for mergesort
After mergesort-ing, result is not a valid list
The result of mergesort is not a valid list; this most likely means it
contains a cycle.
After mergesort-ing, result has incorrect length (expected x, actual length = y)
The result of mergesort-ing must have the same length as the input list.
After mergesort-ing list, result is not sorted
The result of mergesort-ing must be sorted (the actual unsorted results will be printed as part of the check).
After mergesort-ing, result does not contain correct values
The result of mergesort-ing must contain only the values from the input list; this check indicates that some values are missing or new values were added.
After mergesort-ing, result shares some nodes with the input list
While merge must work in-place, not creating new nodes, mergesort must
create an entirely new list, not sharing any nodes with the input list. This
check indicates that the result list shares at least some node*-s with the
input list.