Insertion Sort- inserting from the left

Question

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?

• Ted Brownlow: 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.

Answer 1

• 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!