Sorting algorithms/Insertion sort: Difference between revisions

Content added Content deleted
m (→‎Icon and Unicon: header simplification)
Line 912:
l[j+1] = key</lang>
===Insertion sort with binary search===
<lang python>defimport insertion_sort_bin(seq):bisect
def insertion_sort_bin(seq):
for i in range(1, len(seq)):
key =bisect.insort(seq, seq[.pop(i), 0, i])</lang>
 
# invariant: ``seq[:i]`` is sorted
# 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:]</lang>
=={{header|R}}==
Direct translation of pseudocode.
Retrieved from "https://rosettacode.org/wiki/Sorting_algorithms/Insertion_sort"