# Insertion Sort- inserting from the left

I've implemented my own insertion sort algorithm, and here's the code.

def insertion(lst):
for i in range(1, len(lst)):
for j in range(i):
if lst[i] < lst[j]:
val = lst[i]
del lst[i]
lst.insert(j, val)
break
return lst


Typical insertion sort algorithms seem to compare values from the immediate left of the current index and make swaps as you continue left in the sorted values.

I implemented my algorithm such that it will compare values from left to right (the second for loop). Do you see any issues with my code, or do you have any feedback on this?

• Just a style comment - if you mutate the original list, I would recommend returning None. I personally find it confusing when a function both modifies the input and then returns the reference back to me. – Ted Brownlow Apr 15 at 3:09

• The typical insertion sort is O(n) for already sorted input, and "almost O(n)" for "almost sorted" input. Which is somewhat common in real world data. Your way you don't have that, you're $$\\Theta(n^2)\$$. Someone not familiar with how lists work internally might think your code is O(n) for reverse-sorted input, but since del lst[i] takes O(n - i) and lst.insert(j, val) takes O(n - j), that's not the case.
• As Ted points out, better don't both modify and return. Choose one or the other. Just like Python's own sorting functions do: list.sort only modifies, and sorted only returns (well, it necessarily "modifies" a given iterator by consuming it).
• "Insertion a list"... huh? insertion seems like an incomplete name for insertion sort. You can't really tell from the function signature what it does (and there's no doc string, either).
• I'd go with enumerate, then you have val already, which is nicer and faster.

Improved version sticking with search-from-left but incorporating the other points:

def insertion_sort(lst):
for i, val in enumerate(lst):
for j in range(i):
if val < lst[j]:
del lst[i]
lst.insert(j, val)
break


A benchmark sorting 10000 random numbers:

2.17 seconds  insertion
1.69 seconds  insertion_sort

2.15 seconds  insertion
1.66 seconds  insertion_sort

2.17 seconds  insertion
1.69 seconds  insertion_sort


Benchmark code:

from timeit import timeit
from random import random

def insertion(lst):
for i in range(1, len(lst)):
for j in range(i):
if lst[i] < lst[j]:
val = lst[i]
del lst[i]
lst.insert(j, val)
break
# return lst

def insertion_sort(lst):
for i, val in enumerate(lst):
for j in range(i):
if val < lst[j]:
del lst[i]
lst.insert(j, val)
break

for _ in range(3):
lst = [random() for _ in range(10000)]
for func in insertion, insertion_sort:
copy = lst * 1
t = timeit(lambda: func(copy), number=1)
assert copy == sorted(lst)
print('%.2f seconds ' % t, func.__name__)
print()


Try it online!