Sorting algorithms/Insertion sort: Difference between revisions

Content added Content deleted

Inline

@@ Line 912: / Line 912: @@
         l[j+1] = key</lang>
 ===Insertion sort with binary search===
-<lang python>def insertion_sort_bin(seq):
+<lang python>import bisect
+def insertion_sort_bin(seq):
     for i in range(1, len(seq)):
-        key = seq[i]
+        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.