Sorting algorithms/Insertion sort: Difference between revisions

Content added Content deleted

Inline

Revision as of 04:59, 22 July 2010

An O(n²) sorting algorithm which moves elements one at a time into the correct position. The algorithm consists of inserting one element at a time into the previously sorted part of the array, moving higher ranked elements up as necessary. To start off, the first (or smallest, or any arbitrary) element of the unsorted array is considered to be the sorted part.

Although insertion sort is an O(n²) algorithm, its simplicity, low overhead, good locality of reference and efficiency make it a good choice in two cases (i) small n, (ii) as the final finishing-off algorithm for O(n logn) algorithms such as mergesort and quicksort.

The algorithm is as follows (from the wikipedia):

function insertionSort(array A)
    for i from 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
        done
        A[j+1] = value
    done

Writing the algorithm for integers will suffice.

ActionScript

<lang ActionScript>function insertionSort(array:Array) { for(var i:int = 1; i < array.length;i++) { var value = array[i]; var j:int = i-1; while(j >= 0 && array[j] > value) { array[j+1] = array[j]; j--; } array[j+1] = value; } return array; }</lang>

Ada

<lang 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;
  Value : Integer;
  J     : 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;</lang>

ALGOL 68

Translation of: Ada

Works with: ALGOL 68 version Standard - no extensions to language used

Works with: ALGOL 68G version Any - tested with release mk15-0.8b.fc9.i386

Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386

<lang algol68>MODE DATA = REF CHAR;

PROC in place insertion sort = (REF[]DATA item)VOID: BEGIN

  INT first := LWB item;
  INT last  := UPB item;
  INT j;
  DATA value;
  FOR i FROM first + 1 TO last DO
     value := item[i];
     j := i - 1;
  #  WHILE j >= LWB item AND j <= UPB item ANDF item[j] > value DO // example of ANDF extension #
     WHILE ( j >= LWB item AND j <= UPB item | item[j]>value | FALSE ) DO # no extension! #
        item[j + 1] := item[j];
        j -:=  1
     OD;
     item[j + 1] := value
  OD

END # in place insertion sort #;

[32]CHAR data := "big fjords vex quick waltz nymph"; [UPB data]DATA ref data; FOR i TO UPB data DO ref data[i] := data[i] OD; in place insertion sort(ref data); FOR i TO UPB ref data DO print(ref data[i]) OD; print(new line); print((data))</lang> Output:

abcdefghiijklmnopqrstuvwxyz
big fjords vex quick waltz nymph
<pre>

=={{header|AutoHotkey}}==
contributed by Laszlo on the ahk [http://www.autohotkey.com/forum/post-276481.html#276481 forum]
<lang AutoHotkey>MsgBox % InsertionSort("")
MsgBox % InsertionSort("xxx")
MsgBox % InsertionSort("3,2,1")
MsgBox % InsertionSort("dog,000000,xx,cat,pile,abcde,1,cat,zz,xx,z")

InsertionSort(var) {                     ; SORT COMMA SEPARATED LIST
   StringSplit a, var, `,                ; make array, size = a0
   Loop % a0-1 {
      i := A_Index+1, v := a%i%, j := i-1
      While j>0 and a%j%>v
         u := j+1, a%u% := a%j%, j--
      u := j+1, a%u% := v
   }
   Loop % a0                             ; construct string from sorted array
      sorted .= "," . a%A_Index%
   Return SubStr(sorted,2)               ; drop leading comma
}</lang> 

=={{header|AWK}}==
Sort standard input (storing lines into an array) and output to standard output
<lang awk>{
  line[NR] = $0
}
END { # sort it with insertion sort
  for(i=1; i <= NR; i++) {
    value = line[i]
    j = i - 1
    while( ( j > 0) && ( line[j] > value ) ) {
      line[j+1] = line[j]
      j--
    }
    line[j+1] = value
  }
  #print it
  for(i=1; i <= NR; i++) {
    print line[i]
  }
}</lang>

=={{header|BASIC}}==
{{works with|QBasic}}

This version (which is a translation of the REALbasic version immediately below) should work on any BASIC that can accept arrays as function arguments.
<lang qbasic>DECLARE SUB InsertionSort (theList() AS INTEGER)

DIM n(10) AS INTEGER, L AS INTEGER, o AS STRING
FOR L = 0 TO 10
    n(L) = INT(RND * 32768)
NEXT
InsertionSort n()
FOR L = 1 TO 10
    PRINT n(L); ";";
NEXT

SUB InsertionSort (theList() AS INTEGER)
    DIM insertionElementIndex AS INTEGER
    FOR insertionElementIndex = 1 TO UBOUND(theList)
        DIM insertionElement AS INTEGER
        insertionElement = theList(insertionElementIndex)
        DIM j AS INTEGER
        j = insertionElementIndex - 1
        DO WHILE (j >= 0)
            'necessary for BASICs without short-circuit evaluation
            IF (insertionElement < theList(j)) THEN
                theList(j + 1) = theList(j)
                j = j - 1
            ELSE
                EXIT DO
            END IF
        LOOP
        theList(j + 1) = insertionElement
    NEXT
END SUB</lang>

Sample output:
 1486 ; 9488 ; 9894 ; 17479 ; 18989 ; 23119 ; 23233 ; 24927 ; 25386 ; 26689 ;

{{works with|REALbasic}}
<lang vb> Sub InsertionSort(theList() as Integer)
  for insertionElementIndex as Integer = 1 to UBound(theList)
    dim insertionElement as Integer = theList(insertionElementIndex)
    dim j as Integer = insertionElementIndex - 1
    while (j >= 0) and (insertionElement < theList(j))
      theList(j + 1) = theList(j)
      j = j - 1
    wend
    theList(j + 1) = insertionElement
  next
 End Sub</lang>

=={{header|C}}==
<lang c>#include <stdio.h>
 
void Isort(int a[], int size)
{
  int i, j, temp;
  
  for(i=1; i<=size-1; i++)
  {
    temp = a[i];
    j = i-1;
    while(j>=0 && a[j] > temp)
    {
      a[j+1] = a[j];
      j -= 1;
    }
    a[j+1] = temp;
  }
}
 
int main (int argc, char *argv[])
{
  int intArray[] = {4, 65, 2, -31, 0, 99, 2, 83, 782, 1};
  int i, n;
 	
  n = sizeof(intArray)/sizeof(intArray[0]);
  Isort(intArray, n);
  for(i=0; i<=n-1; i++)
    printf("%d ", intArray[i]);
}</lang>

=={{header|C++}}==
Faster than the basic algorithm because std::lower_bound() finds the insertion position in logarithmic time. Insertion itself, performed with std::rotate(), is still linear.

<lang cpp>#include <algorithm>
#include <vector>

void Isort(std::vector<int>& v)
{
        for (std::vector<int>::iterator i=v.begin(); i!=v.end(); ++i)
                rotate(lower_bound(v.begin(), i, *i), i, i+1);
}</lang>
=={{header|C sharp|C#}}==
<lang csharp>using System;

namespace insertionsort
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] A = new int[] { 3, 9, 4, 6, 8, 1, 7, 2, 5 };
            insertionSort(ref A);
            Console.WriteLine(string.Join(",", A));
        }

        public static void insertionSort (ref int[] A){
            for (int i = 0; i < A.Length; i++)
            {
                int value = A[i], j = i-1;
                while (j >= 0 && A[j] > value)
                {
                    A[j + 1] = A[j];
                    j--;
                }
                A[j + 1] = value;
            }
        }
    }
}
</lang>
=={{header|Clojure}}==
Translated from the Haskell example:
<lang lisp>(defn in-sort! [data]
  (letfn [(insert ([raw x](insert [] raw x))
		  ([sorted [y & raw] x]
		     (if (nil? y) (conj sorted x)
			 (if (<= x y ) (concat sorted [x,y] raw)
			     (recur (conj sorted y)  raw x )))))]	
    (reduce insert [] data)))
;Usage:(in-sort! [6,8,5,9,3,2,1,4,7])
;Returns: [1 2 3 4 5 6 7 8 9]</lang>

=={{header|Common Lisp}}==
<lang 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))</lang>

=={{header|D}}==
<lang 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);
}</lang>
=={{header|E}}==
{{Lines_too_long}}
A direct conversion of the pseudocode.

<lang e>def insertionSort(array) {
    for i in 1..!(array.size()) {
        def value := array[i]
        var j := i-1
        while (j >= 0 && array[j] > value) {
            array[j + 1] := array[j]
            j -= 1
        }
        array[j+1] := value
   }
}</lang>

Test case:

<lang e>? def a := [71, 53, 22, 24, 83, 54, 39, 78, 65, 26, 60, 75, 67, 27, 52, 59, 93, 62, 85, 99, 88, 10, 91, 85, 13, 17, 14, 96, 55, 10, 61, 94, 27, 50, 75, 40, 47, 63, 10, 23].diverge()
> insertionSort(a)
> a
# value: [10, 10, 10, 13, 14, 17, 22, 23, 24, 26, 27, 27, 39, 40, 47, 50, 52, 53, 54, 55, 59, 60, 61, 62, 63, 65, 67, 71, 75, 75, 78, 83, 85, 85, 88, 91, 93, 94, 96, 99].diverge()</lang>

=={{header|Eiffel}}==
{{works with|EiffelStudio|6.6 (with provisional loop syntax)}}

This solution is shown in the routine <code lang="eiffel">sort</code> of the class <code lang="eiffel">MY_SORTED_SET</code>. 

For a more complete explanation of the Eiffel sort examples, see the [[Sorting algorithms/Bubble sort#Eiffel|Bubble sort]].

<lang eiffel>class
    MY_SORTED_SET [G -> COMPARABLE]
inherit
    TWO_WAY_SORTED_SET [G]
        redefine
            sort
        end
create
    make

feature
    sort
            -- Insertion sort
        local
            l_j: INTEGER
            l_value: like item
        do
            across 2 |..| count as ii loop
                from
                    l_j := ii.item - 1
                    l_value := Current.i_th (ii.item)
                until
                    l_j < 1 or Current.i_th (l_j) <= l_value
                loop
                    Current.i_th (l_j + 1) := Current.i_th (l_j)
                    l_j := l_j - 1
                end
                Current.i_th (l_j + 1) := l_value
            end
        end

end</lang>

=={{header|Emacs Lisp}}==
<lang lisp>

(defun min-or-max-of-2-numbers (n1 n2 rel)
  "n1 and n2 are two numbers, rel can be '< or '> according to
what sort of sorting is wanted, this function returns the greater
or smaller number n1 or n2"
  (cond
   ((eval (list rel n1 n2)) n1)
   (t n2)))
  
(defun min-or-max-of-a-list (lon rel)
  "lon is a list of numbers, rel is '< or '>, this fonction
returns the higher or lower number of the list"
  (if (cdr lon)
      (min-or-max-of-2-numbers (car lon) 
			       (min-or-max-of-a-list (cdr lon) rel) 
			       rel)
    (car lon)))

(defun remove-number-from-list (n lon)
  "lon is a list of numbers, n is a number belonging to the list,
this function returns the same list but the number n. If n is
present twice or more, it will be removed only once"
  (if lon
      (cond
       ((= (car lon) n) (cdr lon))
       (t (cons (car lon) (remove-number-from-list n (cdr lon)))))
    nil))


(defun sort-insertion (lon rel)
  "lon is a list of numbers, rel can be '< or '>, this function
returns a list containing the same elements but which is sorted
according to rel"
  (if lon
      (cons (min-or-max-of-a-list lon rel)
	    (sort-insertion 
	     (remove-number-from-list
	      (min-or-max-of-a-list lon rel)
	      lon)
	     rel))
    nil))

;;; let's try it :

(sort-insertion (list 1 2 3 9 8 7 25 12 3 2 1) '>)

</lang>

=={{header|Erlang}}==
<lang Erlang>-module(sort).
-export([insertion/1]).

insertion(L) -> lists:foldl(fun insert/2, [], L).

insert(X,[]) -> [X];
insert(X,L=[H|_]) when X =< H -> [X|L];
insert(X,[H|T]) -> [H|insert(X, T)].</lang>

And the calls:
<lang erlang>1> c(sort).
{ok,sort}
2> sort:insertion([5,3,9,4,1,6,8,2,7]).
[1,2,3,4,5,6,7,8,9]</lang>

=={{header|Forth}}==
<lang 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</lang>

=={{header|Fortran}}==
<lang 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</lang>
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
<lang fortran>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</lang>

=={{header|Haskell}}==
<lang haskell>import Data.List (insert)

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]</lang>

=={{header|HicEst}}==
<lang hicest>DO i = 2, LEN(A)
   value = A(i)
   j = i - 1
 1 IF( j > 0 ) THEN
     IF( A(j) > value ) THEN
       A(j+1) = A(j)
       j = j - 1
       GOTO 1 ! no WHILE in HicEst
     ENDIF
   ENDIF
   A(j+1) = value
ENDDO</lang>

=={{header|J}}==
{{eff note|J|/:~}}
Solution inspired by the Common LISP solution:
<lang J>isort=:((>: # ]) , [ , < #])/</lang>
Example of use:
<lang J>   isort 32 4 1 34 95 3 2 120 _38
_38 1 2 3 4 32 34 95 120</lang>

=={{header|Java}}==
<lang java5>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;
  }
}</lang>
=={{header|Io}}==

<lang io>
List do(
  insertionSortInPlace := method(
    for(j, 1, size - 1,
      key := at(j)
      i := j - 1

      while(i >= 0 and at(i) > key,
        atPut(i + 1, at(i))
        i = i - 1
      )
      atPut(i + 1, key)
    )
  )
)

lst := list(7, 6, 5, 9, 8, 4, 3, 1, 2, 0)
lst insertionSortInPlace println # ==> list(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)</lang>

A shorter, but slightly less efficient, version:
<lang io>List do(
    insertionSortInPlace := method(
        # In fact, we could've done slice(1, size - 1) foreach(...)
        # but creating a new list in memory can only make it worse.
        foreach(idx, key,
            newidx := slice(0, idx) map(x, x > key) indexOf(true)
            if(newidx, insertAt(removeAt(idx), newidx))
        )
    self)
)

lst := list(7, 6, 5, 9, 8, 4, 3, 1, 2, 0)
lst insertionSortInPlace println # ==> list(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
</lang>

=={{header|Lua}}==

<lang lua>function bins(tb, val, st, en)
  local st, en = st or 1, en or #tb
  local mid = math.floor((st + en)/2)
  if en == st then return tb[st] > val and st or st+1
  else return tb[mid] > val and bins(tb, val, st, mid) or bins(tb, val, mid+1, en)
  end
end
function isort(t)
  local ret = {t[1], t[2]}
  for i = 3, #t do
    table.insert(ret, bins(ret, t[i]), t[i])
  end
  return ret
end

print(unpack(isort{4,5,2,7,8,3}))</lang>

=={{header|MATLAB}}==
This is a direct translation of the pseudo-code above, except that it has been modified to compensate for MATLAB's 1 based arrays.
<lang MATLAB>function list = insertionSort(list)

    for i = (2:numel(list))
        
        value = list(i);
        j = i - 1;
        
        while (j >= 1) && (list(j) > value)
            list(j+1) = list(j);
            j = j-1;
        end
        
        list(j+1) = value;
                   
    end %for
end %insertionSort</lang>

Sample Usage:
<lang MATLAB>>> insertionSort([4 3 1 5 6 2])

ans =

     1     2     3     4     5     6</lang>


=={{header|Modula-3}}==
{{trans|Ada}}
<lang modula3>MODULE InsertSort;

PROCEDURE IntSort(VAR item: ARRAY OF INTEGER) =
  VAR j, value: INTEGER;
  BEGIN
    FOR i := FIRST(item) + 1 TO LAST(item) DO
      value := item[i];
      j := i - 1;
      WHILE j >= FIRST(item) AND item[j] > value DO
        item[j + 1] := item[j];
        DEC(j);
      END;
      item[j + 1] := value;
    END;
  END IntSort;
END InsertSort.</lang>

=={{header|OCaml}}==
<lang 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];;</lang>

=={{header|Oz}}==
Direct translation of pseudocode. In-place sorting of mutable arrays.
<lang oz>declare
  proc {InsertionSort A}
     Low = {Array.low A}
     High = {Array.high A}
  in
     for I in Low+1..High do
        Value = A.I
        J = {NewCell I-1}
     in
        for while:@J >= Low andthen A.@J > Value do
           A.(@J+1) := A.@J
           J := @J - 1
        end
        A.(@J+1) := Value
     end
  end

  Arr = {Tuple.toArray unit(3 1 4 1 5 9 2 6 5)}
in
  {InsertionSort Arr}
  {Show {Array.toRecord unit Arr}}</lang>

=={{header|Perl}}==
<lang 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";</lang>
Output:
 -31 0 1 2 4 65 83 99 782
=={{header|PHP}}==
<lang php>function insertionSort(&$arr){
	for($i=0;$i<count($arr);$i++){
		$val = $arr[$i];
		$j = $i-1;
		while($j>=0 && $arr[$j] > $val){
			$arr[$j+1] = $arr[$j];
			$j--;
		}
		$arr[$j+1] = $val;
	}
}

$arr = array(4,2,1,6,9,3,8,7);
insertionSort($arr);
echo implode(',',$arr);</lang>
<pre>1,2,3,4,6,7,8,9

PL/I

<lang pli> INSSORT: PROCEDURE (A);

  DCL  A(*)        FIXED BIN(31);
  DCL (I, J, V, N) FIXED BIN(31);

  N = HBOUND(A,1); M = LBOUND(A,1);
  DO I=M+1 TO N;
     V=A(I);
     J=I-1;
     DO WHILE (J > M-1);
        if A(J) <= V then leave;
        A(J+1)=A(J); J=J-1;
     END;
     A(J+1)=V;
  END;
  RETURN;

END INSSORT; </lang>

Prolog

<lang 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).</lang>

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

PureBasic

<lang PureBasic>Procedure insertionSort(Array a(1))

 Protected low, high
 Protected firstIndex, lastIndex = ArraySize(a())
 
 If lastIndex > firstIndex + 1
   low = firstIndex + 1
   While low <= lastIndex
     high = low
     While high > firstIndex
       If a(high) < a(high - 1)
         Swap a(high), a(high - 1)
       Else
         Break
       EndIf
       high - 1
     Wend
     low + 1
   Wend
 EndIf

EndProcedure</lang>

Python

<lang 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</lang>

Insertion sort with binary search

<lang python>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:]</lang>

R

Direct translation of pseudocode. <lang r>insertionsort <- function(x) {

  for(i in 2:(length(x)))
  {
     value <- x[i]
     j <- i - 1
     while(j >= 1 && x[j] > value)
     {
        x[j+1] <- x[j]
        j <- j-1
     }
     x[j+1] <- value
  }
  x

} insertionsort(c(4, 65, 2, -31, 0, 99, 83, 782, 1)) # -31 0 1 2 4 65 83 99 782</lang>

Ruby

<lang ruby>class Array

 def insertionsort!
   1.upto(length - 1) do |i|
     value = self[i]
     j = i - 1
     while j >= 0 and self[j] > value
       self[j+1] = self[j]
       j -= 1
     end
     self[j+1] = value
   end
   self
 end

end ary = [7,6,5,9,8,4,3,1,2,0] ary.insertionsort!

=> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</lang>

Scala

<lang scala>def insert(list: List[Int], value: Int) = list.span(_ < value) match {

 case (lower, upper) => lower ::: value :: upper

} def insertSort(list: List[Int]) = list.foldLeft(List[Int]())(insert)</lang>

Scheme

<lang 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))</lang>

Seed7

<lang seed7>const proc: insertionSort (inout array elemType: arr) is func

 local
   var integer: i is 0;
   var integer: j is 0;
   var elemType: help is elemType.value;
 begin
   for i range 2 to length(arr) do
     j := i;
     help := arr[i];
     while j > 1 and arr[pred(j)] > help do
       arr[j] := arr[pred(j)];
       decr(j);
     end while;
     arr[j] := help;
   end for;
 end func;</lang>

Original source: [1]

SNOBOL4

<lang snobol>* read data into an array A = table() i = 0 readln A = trim(input) :s(readln) aSize = i - 1

sort array
i = 1 loop1 value = A j = i - 1 loop2 gt(j,0) gt(A<j>,value) :f(done2) A<j + 1> = A<j> j = j - 1 :(loop2) done2 A<j + 1> = value i = ?lt(i,aSize) i + 1 :s(loop1) i = 1
output sorted data
while output = A; i = ?lt(i,aSize) i + 1 :s(while) end</lang>

Standard ML
<lang sml>fun insertion_sort cmp = let
fun insert (x, []) = [x] | insert (x, y::ys) = case cmp (x, y) of GREATER => y :: insert (x, ys) | _ => x :: y :: ys
in
foldl insert []
end;
insertion_sort Int.compare [6,8,5,9,3,2,1,4,7];</lang>
TI-83 BASIC
Store input in L₁, run prgmSORTINS, get output in L₂.
:L₁→L₂ :0→A :Lbl L :A+1→A :A→B :While B>0 :If L₂(B)<L₂(B+1) :Goto B :L₂(B)→C :L₂(B+1)→L₂(B) :C→L₂(B+1) :B-1→B :End :Lbl B :If A<(dim(L₂)-1) :Goto L :DelVar A :DelVar B :DelVar C :Stop
Tcl
<lang tcl>package require Tcl 8.5
proc insertionsort {m} {
for {set i 1} {$i < [llength $m]} {incr i} { set val [lindex $m $i] set j [expr {$i - 1}] while {$j >= 0 && [lindex $m $j] > $val} { lset m [expr {$j + 1}] [lindex $m $j] incr j -1 } lset m [expr {$j + 1}] $val } return $m
}
puts [insertionsort {8 6 4 2 1 3 5 7 9}] ;# => 1 2 3 4 5 6 7 8 9</lang>
TI-83 BASIC
Input into L₁, run prgmSORTINS, output in L₂.
:"INSERTION" :L₁→L₂ :0→A :Lbl L :A+1→A :A→B :While B>0 :If L₂(B)≤L₂(B+1) :Goto B :L₂(B)→C :L₂(B+1)→L₂(B) :C→L₂(B+1) :B-1→B :End :Lbl B :If A<(dim(L₂)-1) :Goto L :DelVar A :DelVar B :DelVar C :Return
UnixPipes
<lang bash>selectionsort() {
read a test -n "$a" && ( selectionsort | sort -nm <(echo $a) -)
}</lang> <lang bash>cat to.sort | selectionsort</lang>
Ursala
<lang Ursala>#import nat
insort = ~&i&& @hNCtX ~&r->lx ^\~&rt nleq-~rlrSPrhlPrSCPTlrShlPNCTPQ@rhPlD</lang> test program: <lang Ursala>#cast %nL
example = insort <45,82,69,82,104,58,88,112,89,74></lang> output:
<45,58,69,74,82,82,88,89,104,112>