Write a Python method sort() to sort a LinkedList object in descending order of the attribute _value. The code for the LinkedList class is shown below and also on the assignment web page. You should use the sorting algorithm described here.

Given a LinkedList object llist, the execution of the code

llist.sort() print(llist)

should cause the sorted list to be printed out.

## DON'T EDIT ANY CODE OTHER THAN THAT OF THE sort() METHOD YOU WRITE. class LinkedList: def __init__(self): self._head = None # sort the nodes in the list def sort(self): # your code here <<< # add a node to the head of the list def add(self, node): node._next = self._head self._head = node # remove a node from the head of the list and return the node def remove(self): assert self._head != None _node = self._head self._head = _node._next _node._next = None return _node # insert node2 after node1 def insert(self, node1, node2): assert node1 != None node2._next = node1._next node1._next = node2 def __str__(self): string = 'List[ ' curr_node = self._head while curr_node != None: string += str(curr_node) curr_node = curr_node.next() string += ']' return string

class Node: def __init__(self, value): self._value = value self._next = None def __str__(self): return str(self._value) + "; " def value(self): return self._value def next(self): return self._next """DO NOT MODIFY ANYTHING BELOW THIS LINE""" def test01(): ll = LinkedList() ll.add(Node(1)) ll.add(Node(3)) ll.add(Node(2)) ll.sort() return str(ll)

def test02(): ll = LinkedList() ll.add(Node(17)) ll.sort() return str(ll)

def test03(): ll = LinkedList() ll.sort() return str(ll)

def test04(): ll = LinkedList() ll.add(Node(1)) ll.add(Node(1)) ll.add(Node(1)) ll.sort() return str(ll)

def test05(): ll = LinkedList() ll.add(Node(3)) ll.add(Node(2)) ll.add(Node(1)) ll.sort() return str(ll)

def ll_sort(test_num): test_func = globals()['test{0}'.format(test_num)] return test_func()