programming problems algorithm to use one extra copy of the list instead of allocating new list each time two lists are merged the extra list is allocated prior to calling the recursive part of the merge sort algorithm thenwith each alternating level of recursion the merge sort algorithm copies to the other listflipping between the two lists to accomplish thisthe mergesortrecursively function should be given new list of lists called lists instead of the seq list at lists [ is the seq list and at lists [ is the extra copy of the list one extra parameter is given to the mergesortrecursively function the index of the list to merge from is also provided this index will flip back and forth between and as each recursive call to mergesortrecursively occurs this flipping of to to and so on can be accomplished using modular arithmetic by writinglisttomergefromindex (listtomergefromindex the percent sign is the remainder after dividing by adding and finding the remainder after dividing by two means that listtomergefromindex flips between and sothe call is made as mergesortrecursively(listtomergefromindexlistsstartstopthe mergesortrecursively function must return the new index of the list to merge from one part of this new mergesortrecursively function is little tricky there may be one more level of recursion on the left or right side for the two recursive calls to mergesortrecursively if this is the casethen the result from either the left or right half must be copied into the same list as the other half before the two halves can be successfully merged when mergesortrecursively returns to the mergesort function the result of sorting may be in the original sequence or it may be in the copy if it is in the copythen the result must be copied back to the original sequence before returning complete this two list version of merge sort as described in this exercise and test it thoroughly then time this version of merge sort and compare those timings with the version of merge sort presented in the and with the quicksort implementation presented in this construct an xml file in the format read by the plotdata py program and plot their corresponding timing diagrams to see how this algorithm performs when compared to the other two complete the tic tac toe program described in the section on -dimensional matrices use the code from sect as your starting point then complete the sections that say they are left as an exercise for the student complete the linkedlist datatype by implementing the deleteequalityiteratelengthand membership operations make sure they have the complexity given in the linkedlist complexities table thenimplement test program in your main function to thorougly test the operations you implemented call the module linkedlist py so that you can import this into other programs that may need it implement queue data type using linked list implementation create set of test cases to throroughly test your datatype place the datatype in file called queue py and create main function that runs your test cases this copy belongs to 'acha