# Difference between revisions of "Insertion sort"

 Related content:

Insertion sort is similar to bubble sort, but is more efficient as it reduces element comparisons somewhat with each pass. An element is compared to all the prior elements until a lesser element is found. In other words, if an element contains a value less than all the previous elements, it compares the element to all the previous elements before going on to the next comparison. Although this algorithm is more efficient than the Bubble sort, it is still inefficient compared to many other sort algorithms since it, and bubble sort, move elements only one position at a time. However, insertion sort is a good choice for small lists (about 30 elements or fewer), and for nearly-sorted lists.

## Implementations

### C

```void insertSort(int a[], size_t 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;
}
}
```

### C++

```template< typename Iterator >
void insertion_sort( Iterator First, Iterator Last )
{
Iterator min = First;
for( Iterator i = First + 1; i < Last; ++i )
if ( *i < *min )
min = i;

std::iter_swap( First, min );
while( ++First < Last )
for( Iterator j = First; *j < *(j - 1); --j )
std::iter_swap( (j - 1), j );
}
```

### 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=j-1;
}
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;
}
}
```

### Common Lisp

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

(defun insertSort (myList)
(if (null mylist)
'()
(insert (first myList) (insertSort (rest myList)))))
```

### Erlang

```insert_sort(L) when is_list(L) ->
insert_sort(L, []).

insert_sort([], Sorted) -> Sorted;
insert_sort([H | T], Sorted) ->
insert_sort(T, insert(H, Sorted)).

insert(X, []) -> [X];
insert(X, Sorted) when X =< hd(Sorted) -> [X | Sorted];
insert(X, [H | T]) -> [H | insert(X, T)].
```

### 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)
```

```import Data.List (insert)

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

### Java

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

#### Generic

```static <T extends Comparable<? super T>> void insertionSort (T[] A) {
for (int i = 1; i < A.length; i++) {
T a = A[i];
int j;
for (j = i - 1; j >=0 && A[j].compareTo(a) > 0; j--)
A[j + 1] = A[j];
A[j + 1] = a;
}
}
```

### OCaml

This implementation uses physical equality to avoid copying sublists that are already sorted:

```# let rec sort = function
| [] -> []
| h1::t as list -> match sort t with
| h2::t when h1>h2 -> h2::sort(h1::t)
| t' -> if t==t' then list else h1::t';;
val sort : 'a list -> 'a list = <fun>
```

For example:

```# sort [1;9;2;8;3;7;4;6;5];;
- : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9]
```

another

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

### Pascal

```PROCEDURE InsertionSort(var Menge: MengeIntegerTyp; Links, Rechts: INTEGER;)
VAR
Index, Einfuegeposition, Zwischenspeicher: INTEGER;
BEGIN
FOR Index := Links + 1 TO Rechts DO
BEGIN
Zwischenspeicher := Menge[Index];
Einfuegeposition := Index;
WHILE ((Menge[Einfugeposition - 1] > Zwischenspeicher) AND
BEGIN
Menge[Einfuegeposition] := Menge[Einfuegeposition - 1];
Einfuegeposition := Einfuegeposition - 1;
END;
Menge[Einfuegeposition] := Zwischenspeicher;
END;
END;
```

### Perl

1:

```sub insertionSort {
my @unsorted = @{\$_[0]};
my @sorted   = @{\$_[1]};

INSERTION:
for my \$current ( @unsorted ) {
for my \$pos ( 0 .. \$#sorted ) {
if ( \$sorted[\$pos] >= \$current ) {
splice @sorted, \$pos, 0, \$current; # Insert \$current
next INSERTION;
}
}

push @sorted, \$current; # No larger value has been found in @sorted
}

return @sorted;
}

my @unsorted = qw(1 82 73 745839 928 7346 8 6 4 8 0 6 34 102);
my @sorted   = qw(1 5);

@sorted = insertionSort(\@unsorted, \@sorted);
```

2:

```sub insert_sort {
for my \$i (0 .. \$#_) {
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 >= 0) && (\$array[\$i-1] > \$temp)){
\$array[\$i] = \$array[\$i-1];
\$i--;
}
\$array[\$i] = \$temp;
}

//Non-decreasing order
for (\$j=1; \$j < count(\$array); \$j++) {
\$key = \$array[\$j];
\$i = \$j - 1;

while(\$i >= 0 and \$array[\$i] > \$key) {
\$array[\$i + 1] = \$array[\$i];
\$i--;
}

\$array[\$i + 1] = \$key;
}

//Non-increasing order
for (\$j=1; \$j < count(\$array); \$j++) {
\$key = \$array[\$j];
\$i = \$j - 1;

while(\$i >= 0 and \$array[\$i] < \$key) {
\$array[\$i + 1] = \$array[\$i];
\$i--;
}

\$array[\$i + 1] = \$key;
}
```

### 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 -= 1
array[insert_index] = removed_value
```

An alternate method:

```def insertsort(array):
for lastsortedelement in range(len(array)-1):
checked = lastsortedelement
while array[checked] > array[lastsortedelement + 1] and checked >= 0:
checked -= 1
#Insert the number into the correct position
array[checked+1], array[checked+2 : lastsortedelement+2] = array[lastsortedelement+1], array[checked+1 : lastsortedelement+1]
return array
```

### Ruby

```def insertion_sort(array)
array.each_with_index do |el,i|
j = i - 1
while j >= 0
break if array[j] <= el
array[j + 1] = array[j]
j -= 1
end
array[j + 1] = el
end
end
```

Another version (used builtin method and binary search):

```def insertion_sort(array)
for i in 1...array.size
w = array.delete_at(i)
l, r = 0, i
while l < r
m = (l + r) / 2
array[m] < w ? l = m + 1 : r = m
end
array.insert(l,w)
end
array
end
```

### Seed7

```const proc: insertionSort (inout array integer: arr) is func
local
var integer: i is 0;
var integer: j is 0;
var integer: help is 0;
begin
for i range 2 to length(arr) do
j := i;
help := arr[i];
while j > 1 and arr[j-1] > help do
a[j] := a[j-1];
decr(j);
end while;
a[j] := help;
end for;
end func;
```

Original source: [1]

### 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;
```

### Turing

```var nombres, limit : int
get nombres
get limit
var sure : boolean := false
var g, smaller : int := 0
var k : int := limit + 1
var last : int := limit
var first : int := 1
var last2 : int := nombres
var br : int := limit - 1
var rann, sort : array 1 .. nombres of int
for i : 1 .. nombres
rann (i) := Rand.Int (0, limit)
sort (i) := k
end for
if rann (1) <= limit then
last := rann (1)
sort (1) := rann (1)
end if
for h : 2 .. upper (rann)
if rann (h) < last then
for decreasing f : nombres - 1 .. 1
sort (f + 1) := sort (f)
end for
sort (1) := rann (h)
last := rann (h)
else
for i : 1 .. upper (rann)
if rann (h) < sort (i) then
for decreasing f : nombres - 1 .. i
sort (f + 1) := sort (f)
end for
sort (i) := rann (h)
exit
end if
end for
end if
end for
for b : 1 .. upper (sort)
put " ", sort (b) ..
end for
```