# 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:
# @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``````

• I used python and got an AC. For my code, I pre-processed the list to check whether it is sorted, which kinda of avoiding the worst case.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.