Sorting algorithms/Insertion 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.

Ada

type Data_Array is array(Natural range <>) of Integer;

procedure Insertion_Sort(Item : in out Data_Array) is
   First : Natural := Item'First;
   Last  : Natural := Item'Last;
   J : Integer;
   Value : Integer;
begin
   for I in (First + 1)..Last loop
      Value := Item(I);
      J := I - 1;
      while J in Item'range and then Item(J) > Value loop
         Item(J + 1) := Item(J);
         J := J - 1;
      end loop;
      Item(J + 1) := Value;
   end loop;
end Insertion_Sort;

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);
}

Forth

: insert ( start end -- start )
  dup @ >r ( r: v )	\ v = a[i]
  begin
    2dup <			\ j>0
  while
    r@ over cell- @ <		\ a[j-1] > v
  while
    cell-			\ j--
    dup @ over cell+ !		\ a[j] = a[j-1]
  repeat then
  r> swap ! ;		\ a[j] = v

: sort ( array len -- )
  1 ?do dup i cells + insert loop drop ;

create test 7 , 3 , 0 , 2 , 9 , 1 , 6 , 8 , 4 , 5 ,
test 10 sort
test 10 cells dump

Fortran

SUBROUTINE Insertion_Sort(a)
  REAL, INTENT(in out), DIMENSION(:) :: a
  REAL :: temp
  INTEGER :: i, j
  
  DO i = 2, SIZE(a)
     j = i - 1
     temp = a(i)
     DO WHILE (j>=1 .AND. a(j)>temp)
        a(j+1) = a(j)
        j = j - 1
     END DO
     a(j+1) = temp
  END DO
END SUBROUTINE Insertion_Sort

In Fortran 90 and above the intrinsic function CSHIFT can be used to shift the elements in the array but in practice is slower than the above example

DO i = 2, SIZE(a)
   j = i - 1
   DO WHILE (j>=1 .AND. a(j) > a(i))
      j = j - 1
   END DO
   a(j+1:i) = cshift(a(j+1:i),-1)
END DO

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;
	}
}

OCaml

<ocaml>let rec insert x = function

 [] -> [x]

| y :: ys ->

  if x <= y then x :: y :: ys
  else y :: insert x ys

let insertion_sort lst = List.fold_right insert lst [];;

insertion_sort [6;8;5;9;3;2;1;4;7];;</ocaml>

Perl

sub insertion_sort {
  $arr = shift;
  for ($i = 0; $i <= $#{$arr}; $i++) {
    $j = $i - 1;
    $key = $arr->[$i];
    while ($arr->[$j] > $key && $j >= 0) {
      $arr->[$j + 1] = $arr->[$j];
        $j -= 1;
      }
    $arr->[$j + 1] = $key;
  }
}

$a = [4, 65, 2, -31, 0, 99, 83, 782, 1];
insertion_sort($a);
print join(' ', @{$a}), "\n";

Output:

-31 0 1 2 4 65 83 99 782

Prolog

insert_sort(L1,L2) :-
  insert_sort_intern(L1,[],L2).

insert_sort_intern([],L,L).
insert_sort_intern([H|T],L1,L) :-
  insert(L1,H,L2),
  insert_sort_intern(T,L2,L).

insert([],X,[X]).
insert([H|T],X,[X,H|T]) :-
  X =< H,
  !.
insert([H|T],X,[H|T2]) :-
  insert(T,X,T2).

% Example use:
%    ?- insert_sort([2,23,42,3,10,1,34,5],L).
%    L = [1,2,3,5,10,23,34,42] ? 
%    yes

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)):
        key = seq[i]
        # 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:]

Scheme

<scheme>(define (insert x lst)

 (if (null? lst)
     (list x)
     (let ((y (car lst))
           (ys (cdr lst)))
       (if (<= x y)
           (cons x lst)
           (cons y (insert x ys))))))

(define (insertion-sort lst)

 (if (null? lst)
     '()
     (insert (car lst)
             (insertion-sort (cdr lst)))))

(insertion-sort '(6 8 5 9 3 2 1 4 7))</scheme>

UnixPipes

selectionsort() {
   read a
   test -n "$a" && ( selectionsort | sort -nm <(echo $a) -)
}

cat to.sort | selectionsort