Sorting algorithms/Insertion sort: Difference between revisions

===Insertion sort with binary search===

<code>

def insertion_sort_bin(seq):

for i in range(1, len(seq)):

# invariant: ``seq[:i]`` is sorted

key = seq[i]

##

# find the least `low' such that ``seq[low]`` is not less then `key'.

# Binary search in sorted sequence ``seq[low:up]``:

low, up = 0, i

while up > low:

middle = (low + up) // 2

if seq[middle] < key:

low = middle + 1

else:

up = middle

##

# insert key at position ``low``

seq[:] = seq[:low] + [key] + seq[low:i] + seq[i + 1:]

return seq

</code>