# Insertion Sort Implementation Efficiency

Is my approach to insertion Sort in Python efficient?

What can be improved efficiency wise?

def insertion_sort(array):
sorted_array = []

for elem in array:
insertion_index = len(sorted_array) #insert at end of list by default
for elem_sorted in sorted_array:
if elem_sorted > elem:
insertion_index = sorted_array.index(elem_sorted)
break
sorted_array.insert(insertion_index, elem)
return sorted_array

num_elems = int(input('Number Of Elements?: '))
array = [int(input(f'Enter Number#{i+1}: ')) for i in range(num_elems)]
a = insertion_sort(array)
print(a)


You are looping over the array elements, and once you find an element greater than the element you are about to insert, you have to again find that element in the array of elements.

        insertion_index = len(sorted_array)
for elem_sorted in sorted_array:
if elem_sorted > elem:
insertion_index = sorted_array.index(elem_sorted)
break


You could instead use enumerate to extract both the element and its index:

        insertion_index = len(sorted_array)
for index, elem_sorted in sorted_array:
if elem_sorted > elem:
insertion_index = index
break


When you search for an element using a for loop and break when you find the element of interest, if you don't find the element, the for loop will execute an optional else: clause, so you don't need to preset the insertion_index:

        for index, elem_sorted in sorted_array:
if elem_sorted > elem:
insertion_index = index
break
else:
insertion_index = len(sorted_array)


# Biggest inefficiency

sorted_array is in sorted order. You could use a binary search to find the insertion location, $$\O(\log N)\$$, instead of a linear search $$\O(N)\$$.

• Second advice is very wrong. Search will be necessarily followed by insertion, which is $O(N)$, and binary serch will drive the overall complexity to $O(N*(N + \log N))$. Insertion sort uses linear search for the reason.
– vnp
Apr 29, 2020 at 4:58
• @vnp Linear search + linear insertion is $O(N + N)$, which is $O(N)$. Binary search + linear search is $O(\log N + N)$, which is still $O(N)$, since $O(\log N) \lt O(N)$. Total complexity is $O(N^2)$ either way. A binary search should still speed up the algorithm, but without improving the overall time complexity. Apr 29, 2020 at 5:07
• Linear search + linear insertion is not $O(N + N)$. This would be the case if the insertion started from the beginning. On the contrary, the insertion starts from the insertion point, which search would return. Together search and insertion do one pass over the array. Compare it with the binary search worst case (all insertions are into the beginning of the array).
– vnp
Apr 29, 2020 at 18:38
• @vnp Shall we continue this in chat Apr 29, 2020 at 22:33