# How to improve O(n^2) python algorithm to ac

• 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:
# @return a ListNode
if not head: return None        # no node
if not hasattr(head, "next"): return None   # head is not a ListNode
# consider head as the last element of the sorted list
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_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
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