I have implemented a typical O(n^2) insertion sort for this problem, however I got TLE on large inputs, when I tried the large input on my desktop, the result is correct. So I am wondering how can I improve the O(n^2) algorithm so that it meets OJ's timing threshold.

```
class Solution:
# @param head, a ListNode
# @return a ListNode
def insertionSortList(self, head):
if not head: return None # no node
if not head.next: return head # only 1 node
if not hasattr(head, "next"): return None # head is not a ListNode
# consider head as the last element of the sorted list
last = head
# we start from head.next
curr = last.next
while curr:
# if last.next > last, it means last.next is sorted as well
if curr.val >= last.val:
last = curr
curr = last.next
continue
# start from insert_loc = head, if insert_loc >= curr, insert it
insert_loc = head
insert_loc_previous = None
# find the location to insert
while curr.val > insert_loc.val and insert_loc_previous != last:
insert_loc_previous = insert_loc # pointer to the previous
insert_loc = insert_loc.next
if not insert_loc_previous: # insert_loc is head
temp = curr.next
curr.next = head
head = curr
last.next = temp
else: # insert in the middle of the sorted list
temp = curr.next
curr.next = insert_loc
insert_loc_previous.next = curr
last.next = temp
curr = last.next
return head
```