Question 3 (18 points): Purpose: To practice working with node chains created using the Node ADT to implement slightly harder Degree of Difficulty: Moderate to Tricky In this question you'll implement merge sort for node chains! Recall, merge sort is a divide-and-conquer technique that uses recursion to sort a given sequence (in this case a node chain). A overview of the algorithm is given below Algorithm mergeSort (NC) # sorts node chain NC using merge sort # NC - a node chain of dat a items # return new sorted node chain of NC if NC contains 0 or 1 data items: return NC divide NC1 firat half of NC NC2 = second half of NC # recursively sort NC1 and NC2 NCI = mergesort(NCI) NC2ergeSort (NC2) conquer !!! NCerge (NC1, NC2) return NC In order to implement merge sort, you are going to write three functions that will make your job easier On Moodle, you can find a starter file called a5q3.py, with all the functions and doc-strings in place, your job is to write the bodies of the functions. You will also find a test script named a5q3 testing.py. It has a bunch of test cases pre-written for you. Read it carefully! Use to.string) from Q1 to help you test and debug your functions. (a) (5 points) Implement the function aplit chain). The interface for the function is: def split.chain (node chain): Purpose: Splita the given node chain in half, returning the second half If the given chain has an odd length, the extra node is part of the second half of the chain Pre-conditiona: Post -conditiona: Return: param node chain: a node-chain, possibly empty the original node chain ia cut in half return: A tuple (nc1, nc2) here nc1 and nc2 are node -chains each containing about half of the nodea in node-chain This function should not create any nodes, and should retum a tuple of references to the two halves of the chain. The tricky part of this is only to remember to put a None at the right place, to terminate the original node-chain about half way through A demonstration of the application of the function is as follows chain5-mode create (3, node create (1 node create (4 node.create (1 print ('chain5 Before:to.string (chain5)) a, bsplit.chain (chain5) print('chain5 After to.string (a)) print ('Second half: to.string (b)) The output from the demonstration is as follows Second half: [ 4 *-)..>[ 1 I *-)..>[ 5 / Notice how the second half of the ist is a little bit larger Hint You may use count,chain) from A5Q2, and integer division b) (5 points) Implement the function merge). The interface for the function is def merge (nci.nc2): Purpose Combine the tvo sorted node - chains ncl and nc2 into a single sorted node chain Pre- conditions: paran nci: anode-chain, possibly empty containing values sorted in ascending order param nc2: a node-chain, possibly empty containing values sorted in ascending order Post condition: None Return :return:a sorted node chain (nc) that contains the values from nci and nc2. If both node chains are empty an empty node -chain vill be returned This one is tricky, as there are a few special cases A demonstration of the application of the function is as follows chainimode create(1. node.create (1 node.create (9))) chain2node create (2, node create (7 node.create (15))) print ('chaini before:to.string (chainl)) print ('chain2 before:to.string (chain2)) merged.chainmerge (chaini, chain2) print chaini after:.to.string (chain1)) print(' chain2 after to.string (chain2)) print('merged.chain after: . to.string (merged.chain)) The output from the demonstration is as follows chaini before:[1l -->1I1-->t9I 1 chain2 before: [ 2 *-1-->[ 7 *-1-->[ 15 / merged.chain after: (c) (3 points) Implement the function merge sort O. The interface for the function is def merge.sort (node_chain) Purpose Sorts the given node chain in ascending order using the nerge sort algorithm Pre-conditions param node.chain:a node- chain, possibly empty. containing only numbers Post - condition the node -chain vill be sorted in ascending order Return return: the node - chain sorted in ascending order Ex:45->1-21-5. Becomes 1-5->21-45 This one might be a little difficult, since it uses recursion A demonstration of the application of the function is as folows chain - node create (10. node create (9. node.create (12. node.create (7. node.create (11. node create (8)>))) print('chain before n.tostring (chain)) sorted_node_chainmerge sort (chain) print ('merge.sort results:ln'to.string (sorted.node.chain)) The output from the demonstration is as follows: cha in before nerge.sort results: d) (5 points) Before you submit your work, review it, and edit it for programming style. Make sure your variables are named well, and that you have appropriate (not excessive) internal documentation (do not change the doc-string which we havegiven youl