Insertion Sort Implementation Efficiency

Question

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)

Answer 1

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)\$.

• vnp: 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.
• AJNeufeld: @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.
• vnp: 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).
• AJNeufeld: @vnp Shall we continue this in chat