We also often sort data structures in order to organize the values stored in them. In this exercise, you will sort a linked list from smallest value to largest value.

To sort a linked list, we can do the following:

- Instantiate a new linked list
- Find the maximum value of our inputted linked list
- Insert the maximum to the beginning of the new linked list
- Remove the maximum value from the inputted linked list
- Repeat steps 2-4 until the head node of the inputted linked list points to
`None`

- Return the new linked list

### Instructions

**1.**

Fill in the `sort_linked_list`

function such that you return a new linked list that is sorted from smallest value to largest value. Step 1 and Step 6 have been completed for you.

Use the methods in **linkedlist.py** and **node.py** to traverse, remove, and get values from the list.

Test cases have been provided for you in order to test your code.

**2.**

Using the steps described in the narrative to write your sort function, what would be the big O runtime of the function? We will learn how to sort data structures with faster runtimes in future courses.

Scroll to the bottom of the code and change the value of `runtime`

to whichever one of these values you think the big O runtime of `sort_linked_list`

is:

`"1"`

`"N"`

`"log N"`

`"N log N"`

`"N^2"`

`"2^N"`

`"N!"`