Sorting algorithms/Insertion sort

Sorting algorithms/Insertion sort
You are encouraged to solve this task according to the task description, using any language you may know.

Sorting Algorithm
This is a sorting algorithm.   It may be applied to a set of data in order to sort it.     For comparing various sorts, see compare sorts.   For other sorting algorithms,   see sorting algorithms,   or:

O(n logn) sorts

Heap sort | Merge sort | Patience sort | Quick sort

O(n log²n) sorts
Shell Sort

O(n²) sorts
Bubble sort | Cocktail sort | Cocktail sort with shifting bounds | Comb sort | Cycle sort | Gnome sort | Insertion sort | Selection sort | Strand sort

other sorts
Bead sort | Bogo sort | Common sorted list | Composite structures sort | Custom comparator sort | Counting sort | Disjoint sublist sort | External sort | Jort sort | Lexicographical sort | Natural sorting | Order by pair comparisons | Order disjoint list items | Order two numerical lists | Object identifier (OID) sort | Pancake sort | Quickselect | Permutation sort | Radix sort | Ranking methods | Remove duplicate elements | Sleep sort | Stooge sort | [Sort letters of a string] | Three variable sort | Topological sort | Tree sort

An O(n^2) sorting algorithm which moves elements one at a time into the correct position. The algorithm is as follows (from the wikipedia):

insertionSort(array A)
        for i = 1 to length[A]-1 do
               value = A[i] 
               j = i-1
               while j >= 0 and A[j] > value do 
                        A[j + 1] = A[j]
                        j = j-1
               A[j+1] = value

Writing the algorithm for integers will suffice.

Common Lisp

(defun span (predicate list)
  (let ((tail (member-if-not predicate list)))
    (values (ldiff list tail) tail)))

(defun less-than (x)
  (lambda (y) (< y x)))

(defun insert (list elt)
  (multiple-value-bind (left right) (span (less-than elt) list)
    (append left (list elt) right)))

(defun insertion-sort (list)
  (reduce #'insert list :initial-value nil))

D

import std.stdio: writefln;

void insertionSort(T)(T[] A) {
    for(int i = 1; i < A.length; i++) {
        T value = A[i];
        int j = i - 1;
        while (j >= 0 && A[j] > value) {
            A[j + 1] = A[j];
            j = j - 1;
        }
        A[j+1] = value;
    }
}

void main() {
    auto a1 = [4, 65, 2, -31, 0, 99, 2, 83, 782, 1];
    insertionSort(a1);
    writefln(a1);
    auto a2 = [4.0,65.0,2.0,-31.0,0.0,99.0,2.0,83.0,782.0,1.0];
    insertionSort(a2);
    writefln(a2);
}

Haskell

insert x [] = [x]
insert x (y:ys) | x <= y    = x:y:ys
insert x (y:ys) | otherwise = y:(insert x ys)

insertionSort :: Ord a => [a] -> [a]
insertionSort = foldr insert []

-- Example use:
-- *Main> insertionSort [6,8,5,9,3,2,1,4,7]
-- [1,2,3,4,5,6,7,8,9]

Java

public static void insertSort(int[] A){
	for(int i = 1; i < A.length; i++){
		int value = A[i];
		int j = i - 1;
		while(j >= 0 && A[j] > value){
			A[j + 1] = A[j];
			j = j - 1;
		}
		A[j + 1] = value;
	}
}

Python

def insertion_sort(l):
    for i in xrange(1, len(l)):
        j = i-1 
        key = l[i]
        while (l[j] > key) and (j >= 0):
           l[j+1] = l[j]
           j -= 1
        l[j+1] = key

Insertion sort with binary search

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