# Algorithm Implementation/Sorting/Insertion sort

Sorts an array of integers.

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

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

## AutoIt3

```Func insertionSort( ByRef \$array )
For \$i = 1 to Ubound( \$array ) - 1
\$j = \$i - 1
\$temp = \$array[\$i]
While ( \$j >= 0 ) And ( \$array[\$j] > \$temp )
\$array[\$j+1] = \$array[\$j]
\$j -= 1
WEnd
\$array[\$j+1] = \$temp
Next
EndFunc
```

## C/C++

In C:

```void insertSort(int a[], int length)
{
int i, j, value;

for(i = 1; i < length; i++)
{
value = a[i];
for (j = i - 1; j >= 0 && a[j] > value; j--)
{
a[j + 1] = a[j];
}
a[j + 1] = value;
}
}
```

In C++:

```#include <algorithm>

template<class Iterator>
void insertion_sort( Iterator a, Iterator end )
{
std::iter_swap( a, std::min_element( a, end ) );

for ( Iterator b = a; ++b < end; a = b )
for( Iterator c = b; *c < *a; --c, --a )
std::iter_swap( a, c );
}
```

In C++, half insertion sort:

```void halfInsertSort(int array[], int length)
{
int begin;
int end;
int middle;
int value;

for (int i = 1; i < length; ++i)
{
value = array[i];
begin = 0;
end = i - 1;
while (begin <= end)
{
middle = (begin + end) / 2;
if (value < array[middle])
{
end = middle - 1;
}
else
{
begin = middle + 1;
}
}

for (int j = i - 1; j >= begin; --j)
{
array[j + 1] = array[j];
}

array[begin] = value;
}
}
```

## C#

```static void InsertSort(IComparable[] array)
{
int i, j;

for (i = 1; i < array.Length; i++)
{
IComparable value = array[i];
j = i - 1;
while ((j >= 0) && (array[j].CompareTo(value) > 0))
{
array[j + 1] = array[j];
j--;
}
array[j + 1] = value;
}
}
```

## C# 2.0

This example sorts a list of objects of any type T that implements IComparable. It demonstrates C# 2.0 generics and in particular the "where" clause.

```static void InsertSort<T>(IList<T> list) where T : IComparable<T>
{
int i, j;

for (i = 1; i < list.Count; i++)
{
T value = list[i];
j = i - 1;
while ((j >= 0) && (list[j].CompareTo(value) > 0))
{
list[j + 1] = list[j];
j--;
}
list[j + 1] = value;
}
}
```

## CAML

```let rec insertion_sort l =
match l with
| [] -> []
| (h::n) -> insert h (insertion_sort n)
and insert t l =
match l with
| [] -> [t]
| (h::n) -> if t > h then h::(insert t n)
else t::h::n ;;
```

## Common Lisp

```(defun insert (target list)
(if (null list)
(cons target nil)
(if (<= target (first list))
(cons target list)
(cons (first list) (insert target (rest list))))))

(defun insertSort (myList)
(if (null myList)
nil
(insert (first myList) (insertSort (rest myList)))))
```

## F#

``` let rec insert x l =  match l with
| []    -> [x]
| y::ys -> if x <= y then x::y::ys
else y::insert x ys
and insertsort l = match l with
| []    -> []
| x::xs -> insert x (insertsort xs)
```

## Go

```func InsertionSort(data []int) {
for i, v := range data {
j := i
for ;j > 0 && v < data[j - 1]; j-- {
data[j] = data[j - 1]
}
data[j] = v
}
}
```

## Java

```public static void insertionsort(int[] numbers) {
for (int i = 0; i < numbers.length; i++) {
int copyNumber = numbers[i];
int j = i;
while (j > 0 && copyNumber < numbers[j-1]) {
numbers[j] = numbers[j-1];
j--;
}
numbers[j] = copyNumber;
}
}
```

## JavaScript

```// Assumes all elements are non-null and non-undefined
function insertionSort(sortMe) {
for (var i = 0, j; i < sortMe.length; ++i) {
var tmp = sortMe[i];
for (j = i - 1; j >= 0 && sortMe[j] > tmp; --j)
sortMe[j + 1] = sortMe[j];
sortMe[j + 1] = tmp;
}
}
```

```import Data.List (insert)

insertsort :: Ord a => [a] -> [a]
insertsort  =  foldr insert []
```

## OCaml

### In lists

```let rec insert e = function
h::t when e <= h -> h :: insert e t
| l                -> e :: l

let rec insertion_sort = function
[]   -> []
| h::t -> insert h (insertion_sort t)
```

### shorter version

The insert function is the same as above.

```let rec insert e = function
h::t when e <= h -> h :: insert e t
| l                ->
let insertion_sort xs = List.fold_right insert xs []
```

## Pascal

```Procedure InsertionSort(var ArrayOfOrd: AnyOrdType);
var
Top, InsertionPos: integer;
Cache :string;

Begin
for Top := 1 to length(ArrayOfOrd) - 1 do
begin
Cache := ArrayOfOrd[Top];
InsertionPos := Top;
while (ArrayOfOrd[InsertionPos - 1] > Cache) and (InsertionPos > 0) do
begin
ArrayOfOrd[InsertionPos] := ArrayOfOrd[InsertionPos - 1];
dec(InsertionPos);
end;
ArrayOfOrd[InsertionPos] := Cache;
end;
End;
```

## Perl

```sub insert_sort {
for(my \$i = 1; \$i <= \$#_; \$i++) {
my (\$j, \$val) = (\$i - 1, \$_[\$i]);
\$_[\$j-- + 1] = \$_[\$j] while (\$j >= 0 && \$_[\$j] > \$val);
\$_[\$j+1] = \$val;
}
}
```

## PHP

```for(\$j=1; \$j < count(\$array); \$j++){
\$temp = \$array[\$j];
\$i = \$j;
while((\$i >= 1) && (\$array[\$i-1] > \$temp)){
\$array[\$i] = \$array[\$i-1];
\$i--;
}
\$array[\$i] = \$temp;
}
```

## Python

```def insertsort(array):
for removed_index in range(1, len(array)):
removed_value = array[removed_index]
insert_index = removed_index
while insert_index > 0 and array[insert_index - 1] > removed_value:
array[insert_index] = array[insert_index - 1]
insert_index = insert_index - 1
array[insert_index] = removed_value
```

## Standard ML

```fun insertsort [] = []
| insertsort (x::xs) =
let fun insert (x:real, []) = [x]
| insert (x:real, y::ys) =
if x<=y then x::y::ys
else y::insert(x, ys)
in insert(x, insertsort xs)
end;
```

### shorter version

The insert function is the same as above.

```fun insert (x:real, []) = [x]
| insert (x, y::ys) =
if x <= y then x::y::ys
else y::insert(x, ys)

val insertion_sort = foldr insert []
```

## Ruby

It sorts the original array.

```def insert_sort!(list)
for i in 1..(list.length - 1)
value = list[i]
j = i - 1
while j >= 0 and list[j] > value
list[j + 1] = list[j]
j -= 1
end
list[j + 1] = value
end
end
```

## NASM

C prototype is

```void isort(int *a, int n)
```

Assembler routine is

```isort:
%define a [ebp + 8]
%define n [ebp + 12]
enter 0, 0
pusha
mov ecx, 1
for:
mov ebx, ecx
imul ebx, 4
mov ebx, [ebx]
mov edx, ecx
dec edx
while:
cmp edx, 0
jl while_quit
mov eax, edx
imul eax, 4
cmp ebx, [eax]
jge while_quit
mov esi, [eax]
mov dword [eax + 4], esi
dec edx
jmp while
while_quit:
mov [eax], ebx
inc ecx
cmp ecx, n
jl for
popa
leave
ret
```

## VB

```Public Sub InsertionSort(ByRef ArrayAngka() As Long)
Dim i, j    As Integer
Dim t       As Long
For i = 0 To (n - 1)
For j = i + 1 To 1 Step -1
If ArrayAngka(j) < ArrayAngka(j - 1) Then
Call tukar(ArrayAngka(j), ArrayAngka(j - 1))
End If
Next j
Next i
End Sub
Private Sub tukar(data1 As Long, data2 As Long)
Dim temp As Long
temp = data1
data1 = data2
data2 = temp
End Sub
```

And here's something a little bit quicker.

```Public Sub Insertionsort(nums() As Long)
Dim i&, j&, k&, length&
length = UBound(nums)
For i = 1 To length
j = nums(i)
k = i
Do While (k > 0) And (nums(k - 1) > j)
nums(k) = nums(k - 1)
k = k - 1
Loop
nums(k) = j
Next i
End Sub
```

## Fortran 90/95

This implementation of Insertion sort follows closely the implementation that can be found in the GPL FORTRAN 90/95 GPL library AFNL.

```! ***********************************
! *
Subroutine Insrt(X, Ipt)
! *
! ***********************************
! * Sort Array X(:) in ascendent order.
! * If present Ipt, a pointer with the
! * changes is returned in Ipt.
! ***********************************

Real (kind=4), Intent (inout) :: X(:)
Integer, Intent (out), Optional :: Ipt(:)

Real (kind=4) :: Rtmp
Integer :: I, J

If (Present(Ipt)) Then
Forall (I=1:Size(X)) Ipt(I) = I

Do I = 2, Size(X)
Rtmp = X(I)
Do J = I-1, 1, -1
If (Rtmp < X(J)) Then
X(J+1) = X(J)
CALL Swap(Ipt, J, J+1)
Else
Exit
End If
End Do
X(J+1) = Rtmp
End Do
Else
Do I = 2, Size(X)
Rtmp = X(I)
Do J = I-1, 1, -1
If (Rtmp < X(J)) Then
X(J+1) = X(J)
Else
Exit
End If
End Do
X(J+1) = Rtmp
End Do
End If

Return
End Subroutine Insrt

! ***********************************
! *
Subroutine Swap(X, I, J)
! *
! ***********************************
! * Swaps elements I and J of array X(:).
! ***********************************

Integer, Intent (inout) :: X(:)
Integer, Intent (in) :: I, J

Integer :: Itmp

Itmp = X(I)
X(I) = X(J)
X(J) = Itmp

Return
End Subroutine Swap
```