Sorting algorithms/Insertion sort

From Rosetta Code
Task
Sorting algorithms/Insertion sort
You are encouraged to solve this task according to the task description, using any language you may know.
This page uses content from Wikipedia. The original article was at Insertion sort. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)


An O(n2) 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(n2) algorithm, its simplicity, low overhead, good locality of reference and efficiency make it a good choice in two cases:

  1.   small   n,
  2.   as the final finishing-off algorithm for O(n logn) algorithms such as mergesort and quicksort.


The algorithm is as follows (from 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.

11l

Translation of: Python
F insertion_sort(&l)
   L(i) 1 .< l.len
      V j = i - 1
      V key = l[i]
      L j >= 0 & l[j] > key
         l[j + 1] = l[j]
         j--
      l[j + 1] = key

V arr = [7, 6, 5, 9, 8, 4, 3, 1, 2, 0]
insertion_sort(&arr)
print(arr)
Output:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

360 Assembly

Translation of: PL/I

These programs use two ASSIST macros (XDECO, XPRNT) to keep the code as short as possible.

Basic

*        Insertion sort            16/06/2016
INSSORT  CSECT
         USING  INSSORT,R13        base register
         B      72(R15)            skip savearea
         DC     17F'0'             savearea
         STM    R14,R12,12(R13)    prolog
         ST     R13,4(R15)         "
         ST     R15,8(R13)         " 
         LR     R13,R15            "
         LA     R6,2               i=2
         LA     R9,A+L'A           @a(2)
LOOPI    C      R6,N               do i=2 to n
         BH     ELOOPI             leave i
         L      R2,0(R9)           a(i)
         ST     R2,V               v=a(i)
         LR     R7,R6              j=i
         BCTR   R7,0               j=i-1
         LR     R8,R9              @a(i)
         S      R8,=A(L'A)         @a(j)
LOOPJ    LTR    R7,R7              do j=i-1 to 1 by -1 while j>0
         BNH    ELOOPJ             leave j
         L      R2,0(R8)           a(j)
         C      R2,V               a(j)>v
         BNH    ELOOPJ             leave j
         MVC    L'A(L'A,R8),0(R8)  a(j+1)=a(j)
         BCTR   R7,0               j=j-1
         S      R8,=A(L'A)         @a(j)
         B      LOOPJ              next j
ELOOPJ   MVC    L'A(L'A,R8),V      a(j+1)=v;
         LA     R6,1(R6)           i=i+1
         LA     R9,L'A(R9)         @a(i)
         B      LOOPI              next i
ELOOPI   LA     R9,PG              pgi=0
         LA     R6,1               i=1
         LA     R8,A               @a(1)
LOOPXI   C      R6,N               do i=1 to n
         BH     ELOOPXI            leave i
         L      R1,0(R8)           a(i)
         XDECO  R1,XDEC            edit a(i)
         MVC    0(4,R9),XDEC+8     output a(i)
         LA     R9,4(R9)           pgi=pgi+1
         LA     R6,1(R6)           i=i+1
         LA     R8,L'A(R8)         @a(i)
         B      LOOPXI             next i
ELOOPXI  XPRNT  PG,L'PG            print buffer
         L      R13,4(0,R13)       epilog 
         LM     R14,R12,12(R13)    "
         XR     R15,R15            "
         BR     R14                exit
A  DC F'4',F'65',F'2',F'-31',F'0',F'99',F'2',F'83',F'782',F'1'
   DC F'45',F'82',F'69',F'82',F'104',F'58',F'88',F'112',F'89',F'74'
V        DS     F                  variable
N        DC     A((V-A)/L'A)       n=hbound(a)
PG       DC     CL80' '            buffer
XDEC     DS     CL12               for xdeco
         YREGS                     symbolics for registers
         END    INSSORT
Output:
 -31   0   1   2   2   4  45  58  65  69  74  82  82  83  88  89  99 104 112 782

Assembler Structured Macros

No harmful gotos [:)Dijkstra], no labels. It's cleaner, but is it clearer?

*        Insertion sort        16/06/2016
INSSORTS CSECT
     USING  INSSORTS,R13       base register
     B      72(R15)            skip savearea
     DC     17F'0'             savearea
     STM    R14,R12,12(R13)    prolog
     ST     R13,4(R15)         "
     ST     R15,8(R13)         " 
     LR     R13,R15            "
     LA     R6,2               i=2
     LA     R9,A+L'A           @a(2)
     DO     WHILE=(C,R6,LE,N)  do while i<=n
       L      R2,0(R9)           a(i)
       ST     R2,V               v=a(i)
       LR     R7,R6              j=i
       BCTR   R7,0               j=i-1
       LR     R8,R9              @a(i)
       S      R8,=A(L'A)         @a(j)
       L      R2,0(R8)           a(j)
       DO     WHILE=(C,R7,GT,0,AND,C,R2,GT,V)  do while j>0 & a(j)>v
         MVC    L'A(L'A,R8),0(R8)  a(j+1)=a(j)
         BCTR   R7,0               j=j-1
         S      R8,=A(L'A)         @a(j)
         L      R2,0(R8)           a(j)
       ENDDO  ,                  next j
       MVC    L'A(L'A,R8),V      a(j+1)=v;
       LA     R6,1(R6)           i=i+1
       LA     R9,L'A(R9)         @a(i)
     ENDDO  ,                  next i
     LA     R9,PG              pgi=0
     LA     R6,1               i=1
     LA     R8,A               @a(1)
     DO     WHILE=(C,R6,LE,N)  do while i<=n
       L      R1,0(R8)           a(i)
       XDECO  R1,XDEC            edit a(i)
       MVC    0(4,R9),XDEC+8     output a(i)
       LA     R9,4(R9)           pgi=pgi+1
       LA     R6,1(R6)           i=i+1
       LA     R8,L'A(R8)         @a(i)
     ENDDO  ,                  next i
     XPRNT  PG,L'PG            print buffer
     L      R13,4(0,R13)       epilog 
     LM     R14,R12,12(R13)    "
     XR     R15,R15            "
     BR     R14                exit
A  DC F'4',F'65',F'2',F'-31',F'0',F'99',F'2',F'83',F'782',F'1'
   DC F'45',F'82',F'69',F'82',F'104',F'58',F'88',F'112',F'89',F'74'
V    DS     F                  variable
N    DC     A((V-A)/L'A)       n=hbound(a)
PG   DC     CL80' '            buffer
XDEC DS     CL12               for xdeco
     YREGS                     symbolics for registers
     END    INSSORTS
Output:

Same as previous

AArch64 Assembly

.section .text
.globl insertion_sort

// C equivalent at bottom
/* void insertion_sort(int *arr, size_t len);
 * X0: pointer to &a[0]
 * X1: index of one past the last element of arr
 * Preconditions:
 * - Arg 1 (X0) is not a null pointer
 * - Arg 2 (X1) is not zero
 */
#define ARR_BEGIN x0
#define ARR_END x2
#define I x3
#define J x4
#define OUTER_TMP w6
#define INNER_TMP w5
insertion_sort:
	add ARR_END, ARR_BEGIN, x1, LSL #2
	add I, ARR_BEGIN, #4
	b 2f
// goto test;
// do {
0:
	ldr OUTER_TMP, [I] // OUTER_TMP = *I;

	// int INNER_TMP, *J;
	// for (J = I; J != &arr[0] && (INNER_TMP = J[-1]) > OUTER_TMP; J--)
	//     *J = INNER_TMP;
	mov J, I
	b 3f
	1:
		// Loop body
		str INNER_TMP, [J], #-4
	3:
		// Loop test
		cmp J, ARR_BEGIN
		b.eq 1f
		ldr INNER_TMP, [J, #-4]
		cmp INNER_TMP, OUTER_TMP
		b.gt 1b
	1:
	str OUTER_TMP, [J] // *J = OUTER_TMP
	add I, I, #4
// test:; } while (I < &arr[len]);
2:
	cmp I, ARR_END
	b.lo 0b
	ret

/*
// First I wrote this C code, then I hand-compiled it to the above assembly.
void insertion_sort(int arr[], size_t len) {
	int x, *pi, *pj;
	for (pi = &a[1]; pi != &arr[len]; pi++) {
		x = *pi;
		for (pj = pi; pj != &a[0] && pj[-1] > x; pj--)
			*pj = pj[-1];
		*pj = x;
	}
}
*/
Works with: as version Raspberry Pi 3B version Buster 64 bits
/* ARM assembly AARCH64 Raspberry PI 3B */
/*  program insertionSort64.s  */
 
/*******************************************/
/* Constantes file                         */
/*******************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeConstantesARM64.inc"

/*********************************/
/* Initialized data              */
/*********************************/
.data
szMessSortOk:       .asciz "Table sorted.\n"
szMessSortNok:      .asciz "Table not sorted !!!!!.\n"
sMessResult:        .asciz "Value  : @ \n"
szCarriageReturn:   .asciz "\n"
 
.align 4
#TableNumber:      .quad   1,3,6,2,5,9,10,8,4,7
TableNumber:     .quad   10,9,8,7,6,-5,4,3,2,1
                 .equ NBELEMENTS, (. - TableNumber) / 8 
/*********************************/
/* UnInitialized data            */
/*********************************/
.bss
sZoneConv:       .skip 24
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main 
main:                                              // entry of program 
    ldr x0,qAdrTableNumber                         // address number table
    mov x1,0                                       // first element
    mov x2,NBELEMENTS                              // number of élements 
    bl insertionSort
    ldr x0,qAdrTableNumber                         // address number table
    bl displayTable
 
    ldr x0,qAdrTableNumber                         // address number table
    mov x1,NBELEMENTS                              // number of élements 
    bl isSorted                                    // control sort
    cmp x0,1                                       // sorted ?
    beq 1f                                    
    ldr x0,qAdrszMessSortNok                       // no !! error sort
    bl affichageMess
    b 100f
1:                                                 // yes
    ldr x0,qAdrszMessSortOk
    bl affichageMess
100:                                               // standard end of the program 
    mov x0,0                                       // return code
    mov x8,EXIT                                    // request to exit program
    svc 0                                          // perform the system call
 
qAdrsZoneConv:            .quad sZoneConv
qAdrszCarriageReturn:     .quad szCarriageReturn
qAdrsMessResult:          .quad sMessResult
qAdrTableNumber:          .quad TableNumber
qAdrszMessSortOk:         .quad szMessSortOk
qAdrszMessSortNok:        .quad szMessSortNok
/******************************************************************/
/*     control sorted table                                   */ 
/******************************************************************/
/* x0 contains the address of table */
/* x1 contains the number of elements  > 0  */
/* x0 return 0  if not sorted   1  if sorted */
isSorted:
    stp x2,lr,[sp,-16]!             // save  registers
    stp x3,x4,[sp,-16]!             // save  registers
    mov x2,0
    ldr x4,[x0,x2,lsl 3]
1:
    add x2,x2,1
    cmp x2,x1
    bge 99f
    ldr x3,[x0,x2, lsl 3]
    cmp x3,x4
    blt 98f
    mov x4,x3
    b 1b
98:
    mov x0,0                       // not sorted
    b 100f
99:
    mov x0,1                       // sorted
100:
    ldp x3,x4,[sp],16              // restaur  2 registers
    ldp x2,lr,[sp],16              // restaur  2 registers
    ret                            // return to address lr x30
/******************************************************************/
/*         insertion sort                                              */ 
/******************************************************************/
/* x0 contains the address of table */
/* x1 contains the first element    */
/* x2 contains the number of element */
insertionSort:
    stp x1,lr,[sp,-16]!        // save  registers
    stp x2,x3,[sp,-16]!        // save  registers
    stp x4,x5,[sp,-16]!        // save  registers
    stp x6,x7,[sp,-16]!        // save  registers
    add x3,x1,1                // index i
1:                             // start loop 1
    ldr x4,[x0,x3,lsl 3]       // load value A[i]
    sub x5,x3,1                // index j
2:                             // start loop 2
    ldr x6,[x0,x5,lsl 3]       // load value A[j]
    cmp x6,x4                  // compare value
    ble 3f 
    add x5,x5,1                // increment index j
    str x6,[x0,x5,lsl 3]       // store value A[j+1}
    sub x5,x5,2                // j = j - 1
    cmp x5,x1                  // compare first element
    bge 2b                     // loop 2
3:
    add x5,x5,1                // increment index j
    str x4,[x0,x5,lsl 3]       // store value A[i}
    add x3,x3,1                // increment index i
    cmp x3,x2                  // end ?
    blt 1b                     // loop 1
 
100:
    ldp x6,x7,[sp],16          // restaur  2 registers
    ldp x4,x5,[sp],16          // restaur  2 registers
    ldp x2,x3,[sp],16          // restaur  2 registers
    ldp x1,lr,[sp],16          // restaur  2 registers
    ret                        // return to address lr x30
 
/******************************************************************/
/*      Display table elements                                */ 
/******************************************************************/
/* x0 contains the address of table */
displayTable:
    stp x1,lr,[sp,-16]!              // save  registers
    stp x2,x3,[sp,-16]!              // save  registers
    mov x2,x0                        // table address
    mov x3,0
1:                                   // loop display table
    ldr x0,[x2,x3,lsl 3]
    ldr x1,qAdrsZoneConv
    bl conversion10S                  // décimal conversion
    ldr x0,qAdrsMessResult
    ldr x1,qAdrsZoneConv
    bl strInsertAtCharInc            // insert result at @ character
    bl affichageMess                 // display message
    add x3,x3,1
    cmp x3,NBELEMENTS - 1
    ble 1b
    ldr x0,qAdrszCarriageReturn
    bl affichageMess
    mov x0,x2
100:
    ldp x2,x3,[sp],16               // restaur  2 registers
    ldp x1,lr,[sp],16               // restaur  2 registers
    ret                             // return to address lr x30
/********************************************************/
/*        File Include fonctions                        */
/********************************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"

ACL2

(defun insert (x xs)
   (cond ((endp xs) (list x))
         ((< x (first xs))
          (cons x xs))
         (t (cons (first xs)
                  (insert x (rest xs))))))

(defun isort (xs)
   (if (endp xs)
       nil
       (insert (first xs)
               (isort (rest xs)))))

Action!

PROC PrintArray(INT ARRAY a INT size)
  INT i

  Put('[)
  FOR i=0 TO size-1
  DO
    IF i>0 THEN Put(' ) FI
    PrintI(a(i))
  OD
  Put(']) PutE()
RETURN

PROC InsertionSort(INT ARRAY a INT size)
  INT i,j,value

  FOR i=1 TO size-1
  DO
    value=a(i)
    j=i-1
    WHILE j>=0 AND a(j)>value
    DO
      a(j+1)=a(j)
      j==-1
    OD
    a(j+1)=value
  OD
RETURN

PROC Test(INT ARRAY a INT size)
  PrintE("Array before sort:")
  PrintArray(a,size)
  InsertionSort(a,size)
  PrintE("Array after sort:")
  PrintArray(a,size)
  PutE()
RETURN

PROC Main()
  INT ARRAY
    a(10)=[1 4 65535 0 3 7 4 8 20 65530],
    b(21)=[10 9 8 7 6 5 4 3 2 1 0
      65535 65534 65533 65532 65531
      65530 65529 65528 65527 65526],
    c(8)=[101 102 103 104 105 106 107 108],
    d(12)=[1 65535 1 65535 1 65535 1
      65535 1 65535 1 65535]
  
  Test(a,10)
  Test(b,21)
  Test(c,8)
  Test(d,12)
RETURN
Output:

Screenshot from Atari 8-bit computer

Array before sort:
[1 4 -1 0 3 7 4 8 20 -6]
Array after sort:
[-6 -1 0 1 3 4 4 7 8 20]

Array before sort:
[10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10]
Array after sort:
[-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10]

Array before sort:
[101 102 103 104 105 106 107 108]
Array after sort:
[101 102 103 104 105 106 107 108]

Array before sort:
[1 -1 1 -1 1 -1 1 -1 1 -1 1 -1]
Array after sort:
[-1 -1 -1 -1 -1 -1 1 1 1 1 1 1]

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

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;

ALGOL 68

Translation of: Ada
Works with: ALGOL 68 version Revision 1 - no extensions to language used
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny
Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d
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))
Output:
abcdefghiijklmnopqrstuvwxyz
big fjords vex quick waltz nymph

ALGOL W

External in-place insertion sort routine for integers. From the pseudo code but with variable bounds.

% insertion sorts in-place the array A. As Algol W procedures can't find the bounds %
% of an array parameter, the lower and upper bounds must be specified in lb and ub  % 
procedure insertionSortI ( integer array A ( * ); integer value lb, ub ) ;
    for i := lb + 1 until ub do begin
        integer v, j;
        v := A( i ); 
        j := i - 1;
        while j >= lb and A( j ) > v do begin
            A( j + 1 ) := A( j );
            j := j - 1
        end while_j_ge_0_and_Aj_gt_v ;
        A( j + 1 ) := v
    end insertionSortI ;

Test the insertionSortI procedure.

begin
    % external in-place insertion sort procedure %
    procedure insertionSortI ( integer array A( * ); integer value lb, ub ) ;
        algol "ISORTI" ;

    integer array d ( 1 :: 8 );
    integer p;
    p := 1;
    for i := 34, 2, -1, 0, 0, 9, -56, 3 do begin
        d( p ) := i;
        p := p + 1
    end for_i ;
    insertionSortI( d, 1, 8 );
    write( i_w := 1, d( 1 ) );
    for i := 2 until 8 do writeon( i_w := 1, d( i ) )
end.
Output:
-56  -1  0  0  2  3  9  34

AppleScript

-- In-place insertion sort
on insertionSort(theList, l, r) -- Sort items l thru r of theList.
    set listLength to (count theList)
    if (listLength < 2) then return
    -- Convert negative and/or transposed range indices.
    if (l < 0) then set l to listLength + l + 1
    if (r < 0) then set r to listLength + r + 1
    if (l > r) then set {l, r} to {r, l}
    
    -- The list as a script property to allow faster references to its items.
    script o
        property lst : theList
    end script
    
    -- Set up a minor optimisation whereby the latest instance of the highest value so far isn't
    -- put back into the list until either it's superseded or the end of the sort is reached.
    set highestSoFar to o's lst's item l
    set rv to o's lst's item (l + 1)
    if (highestSoFar > rv) then
        set o's lst's item l to rv
    else
        set highestSoFar to rv
    end if
    -- Work through the rest of the range, rotating values back into the sorted group as necessary.
    repeat with j from (l + 2) to r
        set rv to o's lst's item j
        if (highestSoFar > rv) then
            repeat with i from (j - 2) to l by -1
                set lv to o's lst's item i
                if (lv > rv) then
                    set o's lst's item (i + 1) to lv
                else
                    set i to i + 1
                    exit repeat
                end if
            end repeat
            set o's lst's item i to rv
        else
            set o's lst's item (j - 1) to highestSoFar
            set highestSoFar to rv
        end if
    end repeat
    set o's lst's item r to highestSoFar
    
    return -- nothing.
end insertionSort
property sort : insertionSort

-- Demo:
local aList
set aList to {60, 73, 11, 66, 6, 77, 41, 97, 59, 45, 64, 15, 91, 100, 22, 89, 77, 59, 54, 61}
sort(aList, 1, -1) -- Sort items 1 thru -1 of aList.
return aList
Output:
{6, 11, 15, 22, 41, 45, 54, 59, 59, 60, 61, 64, 66, 73, 77, 77, 89, 91, 97, 100}

ARM Assembly

Works with: as version Raspberry Pi
/* ARM assembly Raspberry PI  */
/*  program insertionSort.s   */
/* look Pseudocode begin this task  */
 
/************************************/
/* Constantes                       */
/************************************/
.equ STDOUT, 1     @ Linux output console
.equ EXIT,   1     @ Linux syscall
.equ WRITE,  4     @ Linux syscall
/*********************************/
/* Initialized data              */
/*********************************/
.data
szMessSortOk:       .asciz "Table sorted.\n"
szMessSortNok:      .asciz "Table not sorted !!!!!.\n"
sMessResult:        .ascii "Value  : "
sMessValeur:        .fill 11, 1, ' '            @ size => 11
szCarriageReturn:  .asciz "\n"
 
.align 4
iGraine:  .int 123456
.equ NBELEMENTS,      10
#TableNumber:      .int   1,3,6,2,5,9,10,8,4,7
TableNumber:     .int   10,9,8,7,6,5,4,3,2,1
/*********************************/
/* UnInitialized data            */
/*********************************/
.bss  
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main 
main:                                              @ entry of program 
 
1:
    ldr r0,iAdrTableNumber                         @ address number table
    mov r1,#0
    mov r2,#NBELEMENTS                             @ number of élements 
    bl insertionSort
    ldr r0,iAdrTableNumber                         @ address number table
    bl displayTable
 
    ldr r0,iAdrTableNumber                         @ address number table
    mov r1,#NBELEMENTS                             @ number of élements 
    bl isSorted                                    @ control sort
    cmp r0,#1                                      @ sorted ?
    beq 2f                                    
    ldr r0,iAdrszMessSortNok                       @ no !! error sort
    bl affichageMess
    b 100f
2:                                                 @ yes
    ldr r0,iAdrszMessSortOk
    bl affichageMess
100:                                               @ standard end of the program 
    mov r0, #0                                     @ return code
    mov r7, #EXIT                                  @ request to exit program
    svc #0                                         @ perform the system call
 
iAdrsMessValeur:          .int sMessValeur
iAdrszCarriageReturn:    .int szCarriageReturn
iAdrsMessResult:          .int sMessResult
iAdrTableNumber:          .int TableNumber
iAdrszMessSortOk:         .int szMessSortOk
iAdrszMessSortNok:        .int szMessSortNok
/******************************************************************/
/*     control sorted table                                   */ 
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains the number of elements  > 0  */
/* r0 return 0  if not sorted   1  if sorted */
isSorted:
    push {r2-r4,lr}                                    @ save registers
    mov r2,#0
    ldr r4,[r0,r2,lsl #2]
1:
    add r2,#1
    cmp r2,r1
    movge r0,#1
    bge 100f
    ldr r3,[r0,r2, lsl #2]
    cmp r3,r4
    movlt r0,#0
    blt 100f
    mov r4,r3
    b 1b
100:
    pop {r2-r4,lr}
    bx lr                                              @ return 
/******************************************************************/
/*         insertion sort                                              */ 
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains the first element    */
/* r2 contains the number of element */
insertionSort:
    push {r2,r3,r4,lr}                                     @ save registers
    add r3,r1,#1                                           @ start index i
1:                                                         @ start loop
    ldr r4,[r0,r3,lsl #2]                                  @ load value A[i]
    sub r5,r3,#1                                           @ index j
2:
    ldr r6,[r0,r5,lsl #2]                                  @ load value A[j]
    cmp r6,r4                                              @ compare value
    ble 3f
    add r5,#1                                              @ increment index j
    str r6,[r0,r5,lsl #2]                                  @ store value A[j+1]
    sub r5,#2                                              @ j = j - 1
    cmp r5,r1
    bge 2b                                                 @ loop if j >= first item
3:
    add r5,#1                                              @ increment index j
    str r4,[r0,r5,lsl #2]                                  @ store value A[i] in A[j+1]
    add r3,#1                                              @ increment index i
    cmp r3,r2                                              @ end ?
    blt 1b                                                 @ no -> loop

100:
    pop {r2,r3,r4,lr}
    bx lr                                                  @ return 

/******************************************************************/
/*      Display table elements                                */ 
/******************************************************************/
/* r0 contains the address of table */
displayTable:
    push {r0-r3,lr}                                    @ save registers
    mov r2,r0                                          @ table address
    mov r3,#0
1:                                                     @ loop display table
    ldr r0,[r2,r3,lsl #2]
    ldr r1,iAdrsMessValeur                             @ display value
    bl conversion10                                    @ call function
    ldr r0,iAdrsMessResult
    bl affichageMess                                   @ display message
    add r3,#1
    cmp r3,#NBELEMENTS - 1
    ble 1b
    ldr r0,iAdrszCarriageReturn
    bl affichageMess
100:
    pop {r0-r3,lr}
    bx lr
/******************************************************************/
/*     display text with size calculation                         */ 
/******************************************************************/
/* r0 contains the address of the message */
affichageMess:
    push {r0,r1,r2,r7,lr}                          @ save  registres
    mov r2,#0                                      @ counter length 
1:                                                 @ loop length calculation 
    ldrb r1,[r0,r2]                                @ read octet start position + index 
    cmp r1,#0                                      @ if 0 its over 
    addne r2,r2,#1                                 @ else add 1 in the length 
    bne 1b                                         @ and loop 
                                                   @ so here r2 contains the length of the message 
    mov r1,r0                                      @ address message in r1 
    mov r0,#STDOUT                                 @ code to write to the standard output Linux 
    mov r7, #WRITE                                 @ code call system "write" 
    svc #0                                         @ call systeme 
    pop {r0,r1,r2,r7,lr}                           @ restaur des  2 registres */ 
    bx lr                                          @ return  
/******************************************************************/
/*     Converting a register to a decimal unsigned                */ 
/******************************************************************/
/* r0 contains value and r1 address area   */
/* r0 return size of result (no zero final in area) */
/* area size => 11 bytes          */
.equ LGZONECAL,   10
conversion10:
    push {r1-r4,lr}                                 @ save registers 
    mov r3,r1
    mov r2,#LGZONECAL
 
1:	                                            @ start loop
    bl divisionpar10U                               @ unsigned  r0 <- dividende. quotient ->r0 reste -> r1
    add r1,#48                                      @ digit
    strb r1,[r3,r2]                                 @ store digit on area
    cmp r0,#0                                       @ stop if quotient = 0 
    subne r2,#1                                     @ else previous position
    bne 1b	                                    @ and loop
                                                    @ and move digit from left of area
    mov r4,#0
2:
    ldrb r1,[r3,r2]
    strb r1,[r3,r4]
    add r2,#1
    add r4,#1
    cmp r2,#LGZONECAL
    ble 2b
                                                      @ and move spaces in end on area
    mov r0,r4                                         @ result length 
    mov r1,#' '                                       @ space
3:
    strb r1,[r3,r4]                                   @ store space in area
    add r4,#1                                         @ next position
    cmp r4,#LGZONECAL
    ble 3b                                            @ loop if r4 <= area size
 
100:
    pop {r1-r4,lr}                                    @ restaur registres 
    bx lr                                             @return
 
/***************************************************/
/*   division par 10   unsigned                    */
/***************************************************/
/* r0 dividende   */
/* r0 quotient */	
/* r1 remainder  */
divisionpar10U:
    push {r2,r3,r4, lr}
    mov r4,r0                                          @ save value
    //mov r3,#0xCCCD                                   @ r3 <- magic_number lower  raspberry 3
    //movt r3,#0xCCCC                                  @ r3 <- magic_number higter raspberry 3
    ldr r3,iMagicNumber                                @ r3 <- magic_number    raspberry 1 2
    umull r1, r2, r3, r0                               @ r1<- Lower32Bits(r1*r0) r2<- Upper32Bits(r1*r0) 
    mov r0, r2, LSR #3                                 @ r2 <- r2 >> shift 3
    add r2,r0,r0, lsl #2                               @ r2 <- r0 * 5 
    sub r1,r4,r2, lsl #1                               @ r1 <- r4 - (r2 * 2)  = r4 - (r0 * 10)
    pop {r2,r3,r4,lr}
    bx lr                                              @ leave function 
iMagicNumber:  	.int 0xCCCCCCCD

Arturo

insertionSort: function [items][
    arr: new items 
    loop 1..(size items)-1 'i [
        value: arr\[i]
        j: i - 1

        while [and? -> j >= 0 
                    -> value < arr\[j]]
        [
            arr\[j+1]: arr\[j]
            j: j - 1
        ]
        arr\[j+1]: value
    ]
    return arr
]

print insertionSort [3 1 2 8 5 7 9 4 6]
Output:
1 2 3 4 5 6 7 8 9

ATS

For arrays whose elements must not be of linear type

This implementation finds the position at which the element is to be inserted, and then uses array_subcirculate to move it into place. The prelude's implementation of array_subcirculate is a memmove(3).

#include "share/atspre_staload.hats"

(*------------------------------------------------------------------*)
(* Interface                                                        *)

extern fn {a : t@ype}           (* The "less than" template. *)
insertion_sort$lt : (a, a) -<> bool (* Arguments by value. *)

extern fn {a : t@ype}
insertion_sort
          {n   : int}
          (arr : &array (a, n) >> _,
           n   : size_t n)
    :<!wrt> void

(*------------------------------------------------------------------*)
(* Implementation                                                   *)

implement {a}
insertion_sort {n} (arr, n) =
  let
    macdef lt = insertion_sort$lt<a>

    fun
    sort {i : int | 1 <= i; i <= n}
         .<n - i>.
         (arr : &array (a, n) >> _,
          i   : size_t i)
        :<!wrt> void =
      if i <> n then
        let
          fun
          find_new_position
                    {j : nat | j <= i}
                    .<j>.
                    (arr  : &array (a, n) >> _,
                     elem : a,
                     j    : size_t j)
              :<> [j : nat | j <= i] size_t j =
            if j = i2sz 0 then
              j
            else if ~(elem \lt arr[pred j]) then
              j
            else
              find_new_position (arr, elem, pred j)

        val j = find_new_position (arr, arr[i], i)
      in
        if j < i then
          array_subcirculate<a> (arr, j, i);
        sort (arr, succ i)
      end

    prval () = lemma_array_param arr
  in
    if n <> i2sz 0 then
      sort (arr, i2sz 1)
  end

(*------------------------------------------------------------------*)

implement
insertion_sort$lt<int> (x, y) =
  x < y

implement
main0 () =
  let
    #define SIZE 30
    var i : [i : nat] int i
    var arr : array (int, SIZE)
  in
    array_initize_elt<int> (arr, i2sz SIZE, 0);
    for (i := 0; i < SIZE; i := succ i)
      arr[i] := $extfcall (int, "rand") % 10;

    for (i := 0; i < SIZE; i := succ i)
      print! (" ", arr[i]);
    println! ();

    insertion_sort<int> (arr, i2sz SIZE);

    for (i := 0; i < SIZE; i := succ i)
      print! (" ", arr[i]);
    println! ()
  end
Output:

Sorting random numbers.

$ patscc -DATS_MEMALLOC_GCBDW -O3 insertion_sort_task_array_of_nonlinear.dats -lgc && ./a.out
 3 6 7 5 3 5 6 2 9 1 2 7 0 9 3 6 0 6 2 6 1 8 7 9 2 0 2 3 7 5
 0 0 0 1 1 2 2 2 2 2 3 3 3 3 5 5 5 6 6 6 6 6 7 7 7 7 8 9 9 9

For arrays whose elements may be of linear type

If the elements of the array may be of linear type, then it becomes necessary to compare the elements by reference. Furthermore it is necessary to break down the array's view, to obtain views of the elements to be compared. Here, as in the simpler implementation for non-linear elements, I use array_subcirculate to insert an element into its correct position.

(The complications are necessary to prevent us accidentally having two copies of a linear value. Having two copies would introduce such nasty possibilities as a double-free error, use of a destroyed list, etc.)

#include "share/atspre_staload.hats"

(*------------------------------------------------------------------*)
(* Interface                                                        *)

extern fn {a : vt@ype}          (* The "less than" template. *)
insertion_sort$lt : (&a, &a) -<> bool (* Arguments by reference. *)

extern fn {a : vt@ype}
insertion_sort
          {n   : int}
          (arr : &array (a, n) >> _,
           n   : size_t n)
    :<!wrt> void

(*------------------------------------------------------------------*)
(* Implementation                                                   *)

implement {a}
insertion_sort {n} (arr, n) =
  let
    macdef lt = insertion_sort$lt<a>

    fun
    sort {i     : int | 1 <= i; i <= n}
         {p_arr : addr}
         .<n - i>.
         (pf_arr : !array_v (a, p_arr, n) >> _ |
          p_arr  : ptr p_arr,
          i      : size_t i)
        :<!wrt> void =
      if i <> n then
        let
          val pi = ptr_add<a> (p_arr, i)

          fun
          find_new_position
                    {j : nat | j <= i}
                    .<j>.
                    (pf_left : !array_v (a, p_arr, j) >> _,
                     pf_i    : !a @ (p_arr + (i * sizeof a)) |
                     j       : size_t j)
              :<> [j : nat | j <= i] size_t j =
            if j = i2sz 0 then
              j
            else
              let
                prval @(pf_left1, pf_k) = array_v_unextend pf_left

                val k = pred j
                val pk = ptr_add<a> (p_arr, k)
              in
                if ~((!pi) \lt (!pk)) then
                  let
                    prval () = pf_left :=
                      array_v_extend (pf_left1, pf_k)
                  in
                    j
                  end
                else
                  let
                    val new_pos =
                      find_new_position (pf_left1, pf_i | k)
                    prval () = pf_left :=
                      array_v_extend (pf_left1, pf_k)
                  in
                    new_pos
                  end
              end

        prval @(pf_left, pf_right) =
          array_v_split {a} {p_arr} {n} {i} pf_arr
        prval @(pf_i, pf_rest) = array_v_uncons pf_right

        val j = find_new_position (pf_left, pf_i | i)

        prval () = pf_arr :=
          array_v_unsplit (pf_left, array_v_cons (pf_i, pf_rest))
      in
        if j < i then
          array_subcirculate<a> (!p_arr, j, i);
        sort (pf_arr | p_arr, succ i)
      end

    prval () = lemma_array_param arr
  in
    if n <> i2sz 0 then
      sort (view@ arr | addr@ arr, i2sz 1)
  end

(*------------------------------------------------------------------*)

(* The demonstration converts random numbers to linear strings, then
   sorts the elements by their first character. Thus here is a simple
   demonstration that the sort can handle elements of linear type, and
   also that the sort is stable. *)

implement
main0 () =
  let
    implement
    insertion_sort$lt<Strptr1> (x, y) =
      let
        val sx = $UNSAFE.castvwtp1{string} x
        and sy = $UNSAFE.castvwtp1{string} y
        val cx = $effmask_all $UNSAFE.string_get_at (sx, 0)
        and cy = $effmask_all $UNSAFE.string_get_at (sy, 0)
      in
        cx < cy
      end

    implement
    array_initize$init<Strptr1> (i, x) =
      let
        #define BUFSIZE 10
        var buffer : array (char, BUFSIZE)

        val () = array_initize_elt<char> (buffer, i2sz BUFSIZE, '\0')
        val _ = $extfcall (int, "snprintf", addr@ buffer,
                           i2sz BUFSIZE, "%d",
                           $extfcall (int, "rand") % 100)
        val () = buffer[BUFSIZE - 1] := '\0'
      in
        x := string0_copy ($UNSAFE.cast{string} buffer)
      end

    implement
    array_uninitize$clear<Strptr1> (i, x) =
      strptr_free x

    #define SIZE 30
    val @(pf_arr, pfgc_arr | p_arr) =
      array_ptr_alloc<Strptr1> (i2sz SIZE)
    macdef arr = !p_arr

    var i : [i : nat] int i
  in
    array_initize<Strptr1> (arr, i2sz SIZE);

    for (i := 0; i < SIZE; i := succ i)
      let
        val p = ptr_add<Strptr1> (p_arr, i)
        val s = $UNSAFE.ptr0_get<string> p
      in
        print! (" ", s)
      end;
    println! ();

    insertion_sort<Strptr1> (arr, i2sz SIZE);

    for (i := 0; i < SIZE; i := succ i)
      let
        val p = ptr_add<Strptr1> (p_arr, i)
        val s = $UNSAFE.ptr0_get<string> p
      in
        print! (" ", s)
      end;
    println! ();

    array_uninitize<Strptr1> (arr, i2sz SIZE);
    array_ptr_free (pf_arr, pfgc_arr | p_arr)
  end
Output:

Sorting random numbers by their first digit, to demonstrate that the sort is stable. The numbers are stored in the array as linear strings (strings that must be explicitly freed), to demonstrate that the sort works with linear types.

$ patscc -DATS_MEMALLOC_LIBC -O3 insertion_sort_task_array_of_linear.dats && ./a.out
 83 86 77 15 93 35 86 92 49 21 62 27 90 59 63 26 40 26 72 36 11 68 67 29 82 30 62 23 67 35
 15 11 21 27 26 26 29 23 35 36 30 35 49 40 59 62 63 68 67 62 67 77 72 83 86 86 82 93 92 90

For linear lists whose elements may be of linear type

It is useful in a language such as ATS to have a stable insertion sort that operates on singly-linked lists. Such a sort can serve as the innermost part of a list mergesort or list quicksort.

None of the activities in the following implementation requires allocating a new node. The original list is consumed. However, you can use this code to non-destructively sort a non-linear list by first creating a copy, casting the copy to a linear list, and sorting the copy, then casting the result to a non-linear list.

#include "share/atspre_staload.hats"

(*------------------------------------------------------------------*)
(* Interface                                                        *)

extern fn {a : vt@ype}                (* The "less than" template. *)
insertion_sort$lt : (&a, &a) -<> bool (* Arguments by reference. *)

extern fn {a : vt@ype}
insertion_sort
          {n   : int}
          (lst : list_vt (a, n))
    :<!wrt> list_vt (a, n)

(*------------------------------------------------------------------*)
(* Implementation                                                   *)

(* This implementation is based on the insertion-sort part of the
   mergesort code of the ATS prelude.
   
   Unlike the prelude, however, I build the sorted list in reverse
   order. Building the list in reverse order actually makes the
   implementation more like that for an array. *)

(* Some convenient shorthands. *)
#define NIL list_vt_nil ()
#define ::  list_vt_cons

(* Inserting in reverse order minimizes the work for a list already
   nearly sorted, or for stably sorting a list whose entries often
   have equal keys. *)
fun {a : vt@ype}
insert_reverse
          {m       : nat}
          {p_xnode : addr}
          {p_x     : addr}
          {p_xs    : addr}
          .<m>.
          (pf_x  : a @ p_x,
           pf_xs : list_vt (a, 0)? @ p_xs |
           dst   : &list_vt (a, m) >> list_vt (a, m + 1),
           (* list_vt_cons_unfold is a viewtype created by the
              unfolding of a list_vt_cons (our :: operator). *)
           xnode : list_vt_cons_unfold (p_xnode, p_x, p_xs),
           p_x   : ptr p_x,
           p_xs  : ptr p_xs)
    :<!wrt> void =
  (* dst is some tail of the current (reverse-order) destination list.
     xnode is a viewtype for the current node in the source list.
     p_x points to the node's CAR.
     p_xs points to the node's CDR. *)
  case+ dst of
  | @ (y :: ys) =>
    if insertion_sort$lt<a> (!p_x, y) then
      let                     (* Move to the next destination node. *)
        val () = insert_reverse (pf_x, pf_xs | ys, xnode, p_x, p_xs)
        prval () = fold@ dst
      in
      end
    else
      let                       (* Insert xnode here. *)
        prval () = fold@ dst
        val () = !p_xs := dst
        val () = dst := xnode
        prval () = fold@ dst
      in
      end
  | ~ NIL =>
    let                         (* Put xnode at the end. *)
      val () = dst := xnode
      val () = !p_xs := NIL
      prval () = fold@ dst
    in
    end

implement {a}
insertion_sort {n} lst =
  let
    fun                         (* Create a list sorted in reverse. *)
    loop {i : nat | i <= n}
         .<n - i>.
         (dst : &list_vt (a, i) >> list_vt (a, n),
          src : list_vt (a, n - i))
        :<!wrt> void =
      case+ src of
      | @ (x :: xs) =>
        let
          val tail = xs
        in
          insert_reverse<a> (view@ x, view@ xs |
                             dst, src, addr@ x, addr@ xs);
          loop (dst, tail)
        end
      | ~ NIL => ()             (* We are done. *)

    prval () = lemma_list_vt_param lst

    var dst : List_vt a = NIL
  in
    loop (dst, lst);

    (* Reversing a linear list is an in-place operation. *)
    list_vt_reverse<a> dst
  end

(*------------------------------------------------------------------*)

(* The demonstration converts random numbers to linear strings, then
   sorts the elements by their first character. Thus here is a simple
   demonstration that the sort can handle elements of linear type, and
   also that the sort is stable. *)

implement
main0 () =
  let
    implement
    insertion_sort$lt<Strptr1> (x, y) =
      let
        val sx = $UNSAFE.castvwtp1{string} x
        and sy = $UNSAFE.castvwtp1{string} y
        val cx = $effmask_all $UNSAFE.string_get_at (sx, 0)
        and cy = $effmask_all $UNSAFE.string_get_at (sy, 0)
      in
        cx < cy
      end

    implement
    list_vt_freelin$clear<Strptr1> x =
      strptr_free x

    #define SIZE 30

    fn
    create_the_list ()
        :<!wrt> list_vt (Strptr1, SIZE) =
      let
        fun
        loop {i : nat | i <= SIZE}
             .<SIZE - i>.
             (lst : list_vt (Strptr1, i),
              i   : size_t i)
            :<!wrt> list_vt (Strptr1, SIZE) =
          if i = i2sz SIZE then
            list_vt_reverse lst
          else
            let
              #define BUFSIZE 10
              var buffer : array (char, BUFSIZE)

              val () =
                array_initize_elt<char> (buffer, i2sz BUFSIZE, '\0')
              val _ = $extfcall (int, "snprintf", addr@ buffer,
                                 i2sz BUFSIZE, "%d",
                                 $extfcall (int, "rand") % 100)
              val () = buffer[BUFSIZE - 1] := '\0'
              val s = string0_copy ($UNSAFE.cast{string} buffer)
            in
              loop (s :: lst, succ i)
            end
      in
        loop (NIL, i2sz 0)
      end

    var p : List string

    val lst = create_the_list ()

    val () =
      for (p := $UNSAFE.castvwtp1{List string} lst;
           isneqz p;
           p := list_tail p)
        print! (" ", list_head p)
    val () = println! ()

    val lst = insertion_sort<Strptr1> lst

    val () =
      for (p := $UNSAFE.castvwtp1{List string} lst;
           isneqz p;
           p := list_tail p)
        print! (" ", list_head p)
    val () = println! ()

    val () = list_vt_freelin lst
  in
  end
Output:

Sorting random numbers by their first digit, to demonstrate that the sort is stable. The numbers are stored in the list as linear strings (strings that must be explicitly freed), to demonstrate that the sort works if the list elements themselves are linear.

$ patscc -DATS_MEMALLOC_LIBC -O3 insertion_sort_task_linear_list.dats && ./a.out
 83 86 77 15 93 35 86 92 49 21 62 27 90 59 63 26 40 26 72 36 11 68 67 29 82 30 62 23 67 35
 15 11 21 27 26 26 29 23 35 36 30 35 49 40 59 62 63 68 67 62 67 77 72 83 86 86 82 93 92 90

AutoHotkey

contributed by Laszlo on the ahk forum

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
}

AWK

Sort standard input (storing lines into an array) and output to standard output

{
  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]
  }
}

Bash

#!/bin/bash

# Sorting integers with insertion sort

function  insertion_sort ()
{
    # input: unsorted integer array
    # output:  sorted integer array (ascending)
    
    # local variables
    local -a arr         # array
    local -i i           # integers
    local -i j
    local -i key
    local -i prev
    local -i leftval
    local -i N          # size of array

    arr=( $@ )    # copy args into array
   
    N=${#arr[*]}  # arr extent
    readonly N    # make const

    # insertion sort 
    for (( i=1; i<$N; i++ ))  # c-style for loop
    do
	key=$((arr[$i]))      # current value
	prev=$((arr[$i-1]))   # previous value
	j=$i                  # current index
	
	while [ $j -gt 0 ]  && [ $key -lt $prev ]  # inner loop  
	do
	    arr[$j]=$((arr[$j-1])) # shift
	    
	    j=$(($j-1))            # decrement

	    prev=$((arr[$j-1]))    # last value
	    
	done
	
	arr[$j]=$(($key))          # insert key in proper order

    done

    echo ${arr[*]}                   # output sorted array
}

################
function main ()
{
    # main script
    declare -a sorted
   
    # use a default if no cmdline list 
    if [ $# -eq 0 ]; then
	arr=(10 8 20 100 -3 12 4 -5 32 0 1)
    else
	arr=($@) #cmdline list of ints
    fi

    echo
    echo "original"
    echo -e "\t ${arr[*]} \n"

    sorted=($(insertion_sort ${arr[*]}))  # call function

    echo    
    echo "sorted:"
    echo -e "\t ${sorted[*]} \n"
 }   


#script starts here
# source or run
if [[ "$0" == "bash" ]]; then # script is sourced 
    unset main
else
    main "$@"                 # call with cmdline args 
fi

#END
Output:
original
	 10 8 20 100 -3 12 4 -5 32 0 1 

sorted:
	 -5 -3 0 1 4 8 10 12 20 32 100

B4X

The array type can be changed to Object and it will then work with any numeric type.

Sub InsertionSort (A() As Int)
	For i = 1 To A.Length - 1
		Dim value As Int = A(i)
		Dim j As Int = i - 1
		Do While j >= 0 And A(j) > value
			A(j + 1) = A(j)
			j = j - 1
		Loop
		A(j + 1) = value
	Next
End Sub

Sub Test
	Dim arr() As Int = Array As Int(34, 23, 54, 123, 543, 123)
	InsertionSort(arr)
	For Each i As Int In arr
		Log(i)
	Next
End Sub
Output:
23
34
54
123
123
543

BASIC

Translation of: REALbasic
Works with: QBasic

This version should work on any BASIC that can accept arrays as function arguments.

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
Output:
 1486 ; 9488 ; 9894 ; 17479 ; 18989 ; 23119 ; 23233 ; 24927 ; 25386 ; 26689 ;

GW-BASIC

Works with: BASICA
Works with: QBasic
Works with: QuickBASIC
Works with: VB-DOS

Sorts N integers in an array a() with the Insertion sort

10 'SAVE "INSERTGW",A
20 DEFINT A-Z
30 OPTION BASE 1
40 N=20: R=100: I=0: Y=0: V=0: P=0
50 DIM A(N)
60 ' Creates the disordered array
70 CLS: PRINT "This program sorts by Insertion a list of randomly generated numbers."
80 PRINT: PRINT "Unsorted list:"
90 RANDOMIZE TIMER
100 FOR I = 1 TO N
110   A(I) = INT(RND * R) + 1
120 NEXT I
130 GOSUB 260
140 PRINT: PRINT "Sorted list."
150 ' Insertion Sort
160 FOR I=1 TO N
170   V=A(I): P=I-1: S=1
180   WHILE P>0 AND S=1
185     S=0
190     IF A(P) > V THEN A(P+1)=A(P): P=P-1: S=1
200   WEND
210   A(P+1) = V
220 NEXT I
230 GOSUB 260
240 PRINT: PRINT "End of program execution."
250 END
260 ' Print list routine
270   FOR I=1 TO N
280     PRINT A(I);
290   NEXT I
300   PRINT
310 RETURN
Output:
This program sorts by Insertion a list of randomly generated numbers.

Unsorted list:
 73  11  100  68  28  48  3  36  15  34  31  26  47  61  5  58  15  86  69  79

Sorted list:
 3  5  11  15  15  26  28  31  34  36  47  48  58  61  68  69  73  79  86  100

End of program execution.

ZX BASIC

Sorts N elements in array i() into ascending order. Invoke with GO SUB 500.

500 FOR j=1 TO N-1 
510   IF i(j)<=i(j+1) THEN NEXT j: RETURN  
520   LET c=i(j+1) 
530   FOR k=j TO 1 STEP -1: IF i(k)>c THEN LET i(k+1)=i(k): NEXT k 
540   LET i(k+1)=c 
600 NEXT j: RETURN

For those who prefer GO TOs over conditional NEXTs (fine in ZX BASIC but problematic for compilers and stack-dependent interpreters like NextBASIC’s integer extensions) replace NEXT J: RETURN in line 510 with GO TO 600 and use this line 530:

530 IF k>0 THEN IF i(k)>c THEN LET i(k+1)=i(k): LET k=k-1: GO TO 530 

BBC BASIC

Note that the array index is assumed to start at zero.

      DIM test(9)
      test() = 4, 65, 2, -31, 0, 99, 2, 83, 782, 1
      PROCinsertionsort(test(), 10)
      FOR i% = 0 TO 9
        PRINT test(i%) ;
      NEXT
      PRINT
      END
      
      DEF PROCinsertionsort(a(), n%)
      LOCAL i%, j%, t
      FOR i% = 1 TO n%-1
        t = a(i%)
        j% = i%
        WHILE j%>0 AND t<a(ABS(j%-1))
          a(j%) = a(j%-1)
          j% -= 1
        ENDWHILE
        a(j%) = t
      NEXT
      ENDPROC
Output:
       -31         0         1         2         2         4        65        83        99       782

Commodore BASIC

10 DIM A(10): N=9
11 REM GENERATE SOME RANDOM NUMBERS AND PRINT THEM
12 FOR I=0 TO N: A(I)=INT(RND(1)*10)+1: NEXT: GOSUB 50
20 FOR J=1 TO N:KEY=A(J): I=J-1: GOSUB 30: A(I+1)=KEY: NEXT: GOSUB 50: END
30 IFI=-1 THEN RETURN
31 IFA(I)>KEY THEN A(I+1)=A(I):I=I-1: GOTO 30
32 RETURN
50 PRINT: FOR I=0 TO N: PRINTA(I): NEXT: RETURN

IS-BASIC

100 PROGRAM "InserSrt.bas"
110 RANDOMIZE 
120 NUMERIC ARRAY(5 TO 21)
130 CALL INIT(ARRAY)
140 CALL WRITE(ARRAY)
150 CALL INSERTSORT(ARRAY)
160 CALL WRITE(ARRAY)
170 DEF INIT(REF A)
180   FOR I=LBOUND(A) TO UBOUND(A)
190     LET A(I)=RND(98)+1
200   NEXT
210 END DEF
220 DEF WRITE(REF A)
230   FOR I=LBOUND(A) TO UBOUND(A)
240     PRINT A(I);
250   NEXT
260   PRINT
270 END DEF
280 DEF INSERTSORT(REF A)
290   FOR J=LBOUND(A)+1 TO UBOUND(A)
300     LET I=J-1:LET SW=A(J)
310     DO WHILE I>=LBOUND(A) AND SW<A(I)
320       LET A(I+1)=A(I):LET I=I-1
330     LOOP
340     LET A(I+1)=SW
350   NEXT
360 END DEF

BASIC256

Translation of: FreeBASIC
global array
dim array(15)
a = array[?,]
b = array[?]
for i = a to b-1
	array[i] = int(rand * 100)
next i

print "unsort ";
for i = a to b-1
	print rjust(array[i], 4);
next i

call insertionSort(array)  # ordenar el array

print chr(10); "  sort ";
for i = a to b-1
	print rjust(array[i], 4);
next i
end

subroutine insertionSort(array)
	lb = array[?,]

	for i = lb + 1 to array[?]-1
		valor = array[i]
		j = i - 1
		while j >= lb  and array[j] > valor
			array[j +1] = array[j]
			j -= 1
		end while

		array[j+1] = valor
	next i
end subroutine

BCPL

get "libhdr"

let insertionSort(A, len) be
    for i = 1 to len-1 do
    $(  let value = A!i
        let j = i-1
        while j >= 0 & A!j > value do
        $(  A!(j+1) := A!j
            j := j-1
        $)
        A!(j+1) := value
    $)
    
let write(s, A, len) be
$(  writes(s)
    for i=0 to len-1 do writed(A!i, 4)
    wrch('*N')
$)
    
let start() be
$(  let array = table 4,65,2,-31,0,99,2,83,782,1
    let length = 10    
    write("Before: ", array, length)
    insertionSort(array, length)
    write("After:  ", array, length)
$)
Output:
Before:    4  65   2 -31   0  99   2  83 782   1
After:   -31   0   1   2   2   4  65  83  99 782

Binary Lambda Calculus

As documented at https://github.com/tromp/AIT/blob/master/lists/sort.lam, the 55 byte BLC program

15 46 84 06 05 46 81 60 15 fb ec 2f 80 01 5b f9 7f 0b 7e f7 2f ec 2d fb 80 56 05 fd 85 bb 76 11 5d 50 5c 00 8b f3 ff 04 af fe 60 de 57 ff 30 5d 81 ff c2 dd 9a 28 20

sorts a list of bitstrings, such as integers of a fixed bit-width, lexicographically.

C

#include <stdio.h>

void insertion_sort(int*, const size_t); 

void insertion_sort(int *a, const size_t n) {
	for(size_t i = 1; i < n; ++i) {
		int key = a[i];
		size_t j = i;
		while( (j > 0) && (key < a[j - 1]) ) {
			a[j] = a[j - 1];
			--j;
		}
		a[j] = key;
	}
}

int main (int argc, char** argv) {

    int a[] = {4, 65, 2, -31, 0, 99, 2, 83, 782, 1};

    const size_t n = sizeof(a) / sizeof(a[0]) ;   // array extent 

    for (size_t i = 0; i < n; i++)
        printf("%d%s", a[i], (i == (n - 1))? "\n" : " ");

    insertion_sort(a, n);

    for (size_t i = 0; i < n; i++)
        printf("%d%s", a[i], (i == (n - 1))? "\n" : " ");

    return 0;
}
Output:
4 65 2 -31 0 99 2 83 782 1
-31 0 1 2 2 4 65 83 99 782

C#

namespace Sort {
  using System;

  static class InsertionSort<T> where T : IComparable {
    public static void Sort(T[] entries) {
      Sort(entries, 0, entries.Length - 1);
    }

    public static void Sort(T[] entries, Int32 first, Int32 last) {
      for (var i = first + 1; i <= last; i++) {
        var entry = entries[i];
        var j = i;

        while (j > first && entries[j - 1].CompareTo(entry) > 0)
          entries[j] = entries[--j];

        entries[j] = entry;
      }
    }
  }
}

Example:

  using Sort;
  using System;

  class Program {
    static void Main(String[] args) {
      var entries = new Int32[] { 3, 9, 4, 6, 8, 1, 7, 2, 5 };
      InsertionSort<Int32>.Sort(entries);
      Console.WriteLine(String.Join(" ", entries));
    }
  }

C++

Uses C++11. Compile with

g++ -std=c++11 insertion.cpp

Uses binary search via std::upper_bound() to find the insertion position in logarithmic time and then performs the insertion via std::rotate() in linear time.

#include <algorithm>
#include <iostream>
#include <iterator>

// std::rotate is used to shift the sub-region
// if the predicate  p is true
template <typename RandomAccessIterator, typename Predicate>
void insertion_sort(RandomAccessIterator begin, RandomAccessIterator end,
                    Predicate p) {
  for (auto i = begin; i != end; ++i) {
    std::rotate(std::upper_bound(begin, i, *i, p), i, i + 1);
  }
}

// calls with default Predicate std::less (sort ascending)
template <typename RandomAccessIterator>
void insertion_sort(RandomAccessIterator begin, RandomAccessIterator end) {
  insertion_sort(begin, end, std::less<typename std::iterator_traits<RandomAccessIterator>::value_type>());
}


int main() {

  int a[] = { 100, 2, 56, 200, -52, 3, 99, 33, 177, -199 };

  insertion_sort(std::begin(a), std::end(a));

  // 'iterates' numbers to std::cout 
  // converts ints to strings for output to screen
  copy(std::begin(a), std::end(a), std::ostream_iterator<int>(std::cout, " "));
  
std::cout << "\n";
}
Output:
-199 -52 2 3 33 56 99 100 177 200

Clojure

(defn insertion-sort [coll]
   (reduce (fn [result input]
             (let [[less more] (split-with #(< % input) result)]
               (concat less [input] more)))
           []
           coll))

Translated from the Haskell example:

(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]

CLU

% Insertion-sort an array in place. 
insertion_sort = proc [T: type] (a: array[T]) 
              where T has lt: proctype (T,T) returns (bool)

    bound_lo: int := array[T]$low(a)
    bound_hi: int := array[T]$high(a)
     
    for i: int in int$from_to(bound_lo, bound_hi) do
        value: T := a[i]
        j: int := i - 1
        while j >= bound_lo cand value < a[j] do
            a[j+1] := a[j]
            j := j-1
        end
        a[j+1] := value
    end
end insertion_sort

% Print an array
print_arr = proc [T: type] (a: array[T], w: int, s: stream)
            where T has unparse: proctype (T) returns (string)
    for el: T in array[T]$elements(a) do
        stream$putright(s, T$unparse(el), w)
    end
    stream$putc(s, '\n')
end print_arr

start_up = proc ()
    ai = array[int]
    po: stream := stream$primary_output()
    test: ai := ai$[7, -5, 0, 2, 99, 16, 4, 20, 47, 19]
    
    stream$puts(po, "Before: ") print_arr[int](test, 3, po)
    insertion_sort[int](test)
    stream$puts(po, "After:  ") print_arr[int](test, 3, po)
end start_up
Output:
Before:   7 -5  0  2 99 16  4 20 47 19
After:   -5  0  2  4  7 16 19 20 47 99

CMake

# insertion_sort(var [value1 value2...]) sorts a list of integers.
function(insertion_sort var)
  math(EXPR last "${ARGC} - 1")         # Sort ARGV[1..last].
  foreach(i RANGE 1 ${last})
    # Extend the sorted area to ARGV[1..i].
    set(b ${i})
    set(v ${ARGV${b}})
    # Insert v == ARGV[b] in sorted order. While b > 1, check if b is
    # too high, then decrement b. After loop, set ARGV[b] = v.
    while(b GREATER 1)
      math(EXPR a "${b} - 1")
      set(u ${ARGV${a}})
      # Now u == ARGV[a]. Pretend v == ARGV[b]. Compare.
      if(u GREATER ${v})
        # ARGV[a] and ARGV[b] are in wrong order. Fix by moving ARGV[a]
        # to ARGV[b], making room for later insertion of v.
        set(ARGV${b} ${u})
      else()
        break()
      endif()
      math(EXPR b "${b} - 1")
    endwhile()
    set(ARGV${b} ${v})
  endforeach(i)

  set(answer)
  foreach(i RANGE 1 ${last})
    list(APPEND answer ${ARGV${i}})
  endforeach(i)
  set("${var}" "${answer}" PARENT_SCOPE)
endfunction(insertion_sort)
insertion_sort(result 33 11 44 22 66 55)
message(STATUS "${result}") # -- 11;22;33;44;55;66

COBOL

This exerpt contains just enough of the procedure division to show the sort itself. The appropriate data division entries can be inferred. See also the entry for the Bubble sort for a full program.

       C-PROCESS SECTION.
           PERFORM E-INSERTION VARYING WB-IX-1 FROM 1 BY 1
                               UNTIL WB-IX-1 > WC-SIZE.

...

       E-INSERTION SECTION.
       E-000.
           MOVE WB-ENTRY(WB-IX-1) TO WC-TEMP.
           SET WB-IX-2 TO WB-IX-1.

           PERFORM F-PASS UNTIL WB-IX-2 NOT > 1 OR
                                WC-TEMP NOT < WB-ENTRY(WB-IX-2 - 1).

           IF WB-IX-1 NOT = WB-IX-2
              MOVE WC-TEMP TO WB-ENTRY(WB-IX-2).

       E-999.
           EXIT.

       F-PASS SECTION.
       F-000.
           MOVE WB-ENTRY(WB-IX-2 - 1) TO WB-ENTRY(WB-IX-2).
           SET WB-IX-2                DOWN BY 1.

       F-999.
           EXIT.

And a fully runnable version, by Steve Williams

Works with: GnuCOBOL
        >>SOURCE FORMAT FREE
*> This code is dedicated to the public domain
*> This is GNUCOBOL 2.0
identification division.
program-id. insertionsort.
environment division.
configuration section.
repository. function all intrinsic.
data division.
working-storage section.
01  filler.
    03  a pic 99.
    03  a-lim pic 99 value 10.
    03  array occurs 10 pic 99.

01  filler.
    03  s pic 99.
    03  o pic 99.
    03  o1 pic 99.
    03  sorted-len pic 99.
    03  sorted-lim pic 99 value 10.
    03  sorted-array occurs 10 pic 99.

procedure division.
start-insertionsort.

    *> fill the array
    compute a = random(seconds-past-midnight)
    perform varying a from 1 by 1 until a > a-lim
        compute array(a) = random() * 100
    end-perform

    *> display the array
    perform varying a from 1 by 1 until a > a-lim
        display space array(a) with no advancing
    end-perform
    display  space 'initial array'

    *> sort the array
    move 0 to sorted-len
    perform varying a from 1 by 1 until a > a-lim
        *> find the insertion point
        perform varying s from 1 by 1
        until s > sorted-len
        or array(a) <= sorted-array(s)
            continue
        end-perform

        *>open the insertion point
        perform varying o from sorted-len by -1
        until o < s
            compute o1 = o + 1
            move sorted-array(o) to sorted-array(o1)
        end-perform

        *> move the array-entry to the insertion point
        move array(a) to sorted-array(s)

        add 1 to sorted-len
    end-perform

    *> display the sorted array
    perform varying s from 1 by 1 until s > sorted-lim
        display space sorted-array(s) with no advancing
    end-perform
    display space 'sorted array'

    stop run
    .
end program insertionsort.
Output:
prompt$ cobc -xj insertionsort.cob
 89 04 86 32 65 62 83 75 24 69 initial array
 04 24 32 62 65 69 75 83 86 89 sorted array

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))
(defun insertion-sort (sequence &optional (predicate #'<))
  (if (cdr sequence)
      (insert (car sequence)                 ;; insert the current item into
              (insertion-sort (cdr sequence) ;; the already-sorted
                              predicate)     ;; remainder of the list
              predicate)
      sequence)) ; a list of one element is already sorted

(defun insert (item sequence predicate)
  (cond ((null sequence) (list item))
        ((funcall (complement predicate)      ;; if the first element of the list
                              (car sequence)  ;; isn't better than the item,
                              item)           ;; cons the item onto
         (cons item sequence))                ;; the front of the list
        (t (cons (car sequence) ;; otherwise cons the first element onto the front of
                 (insert item   ;; the list of the item sorted with the rest of the list
                         (cdr sequence)
                         predicate)))))
(defgeneric nsrt (sequence predicate))

(defmethod nsrt ((sequence sequence) predicate)
  (loop :for i :from 1 :below (length sequence)
        :do (loop :for j :from i :downto 1
                  :do (let ((current (elt sequence j))
                            (previous (elt sequence (1- j))))
                        (when (funcall predicate current previous)
                          (rotatef (elt sequence j)
                                   (elt sequence (1- j))))))
        :finally (return sequence)))

;; (nsrt "adfcghjiklmnoprbtuvqewysxz" #'char<)
;; => "abcdefghijklmnopqrstuvwxyz"
;; 
;; (nsrt '(who the hecc do you think i am?)
;;       (lambda (x y)
;;         (string< (nsrt (format nil "~a" x) #'char<)
;;                  (nsrt (format nil "~a" y) #'char<))))
;; => (AM? HECC DO THE THINK WHO I YOU)
;; 
;; (nsrt (loop :for i :from 1 :to 1000 :collect (random i))
;;       #'<)
;; => [not printed but works, try it!]


Craft Basic

define size = 10, value = 0

dim list[size]

gosub fill
gosub sort
gosub show

end

sub fill

	for i = 0 to size - 1

		let list[i] = int(rnd * 100)

	next i

return

sub sort

	for i = 1 to size - 1

		let value = list[i]
		let j = i - 1

		do

			if j >= 0 and list[j] > value then

				let p = j + 1
				let list[p] = list[j]
				let j = j - 1

			endif

		loop j >= 0 and list[j] > value

		let p = j + 1
		let list[p] = value

		wait

	next i

return

sub show

	for i = 0 to size - 1

		print i, ": ", list[i]
	
	next i

return

D

void insertionSort(T)(T[] data) pure nothrow @safe @nogc {
    foreach (immutable i, value; data[1 .. $]) {
        auto j = i + 1;
        for ( ; j > 0 && value < data[j - 1]; j--)
            data[j] = data[j - 1];
        data[j] = value;
    }
}

void main() {
    import std.stdio;
    auto items = [28, 44, 46, 24, 19, 2, 17, 11, 25, 4];
    items.insertionSort;
    items.writeln;
}
Output:
[2, 4, 11, 17, 19, 24, 25, 28, 44, 46]

Higher Level Version

Translation of: C++
import std.stdio, std.range, std.algorithm, std.traits;

void insertionSort(R)(R arr)
if (hasLength!R && isRandomAccessRange!R && hasSlicing!R) {
    foreach (immutable i; 1 .. arr.length)
        bringToFront(arr[0 .. i].assumeSorted.upperBound(arr[i]), arr[i .. i + 1]);
}

void main() {
    import std.random, std.container;

    auto arr1 = [28, 44, 46, 24, 19, 2, 17, 11, 25, 4];
    arr1.insertionSort;
    assert(arr1.isSorted);
    writeln("arr1 sorted: ", arr1);

    auto arr2 = Array!int([28, 44, 46, 24, 19, 2, 17, 11, 25, 4]);
    arr2[].insertionSort;
    assert(arr2[].isSorted);
    writeln("arr2 sorted: ", arr2[]);

    // Random data test.
    int[10] buf;
    foreach (immutable _; 0 .. 100_000) {
        auto arr3 = buf[0 .. uniform(0, $)];
        foreach (ref x; arr3)
            x = uniform(-6, 6);
        arr3.insertionSort;
        assert(arr3.isSorted);
    }
}
Output:
arr1 sorted: [2, 4, 11, 17, 19, 24, 25, 28, 44, 46]
arr2 sorted: [2, 4, 11, 17, 19, 24, 25, 28, 44, 46]

Dart

Translation of: Java
insertSort(List<int> array){
  for(int i = 1; i < array.length; i++){
    int value = array[i];
    int j = i - 1;
    while(j >= 0 && array[j] > value){
      array[j + 1] = array[j];
      j = j - 1;
    }
    array[j + 1] = value;
  }
  return array;
}

void main() {
    List<int> a = insertSort([10, 3, 11, 15, 19, 1]);
    print('${a}');
}
Output:
array unsorted: [10, 3, 11, 15, 19, 1];
a sorted: [1, 3, 10, 11, 15, 19]

Delphi

Array sort

Dynamic array is a 0-based array of variable length

Static array is an arbitrary-based array of fixed length

program TestInsertionSort;

{$APPTYPE CONSOLE}

{.$DEFINE DYNARRAY}  // remove '.' to compile with dynamic array

type
  TItem = Integer;   // declare ordinal type for array item
{$IFDEF DYNARRAY}
  TArray = array of TItem;          // dynamic array
{$ELSE}
  TArray = array[0..15] of TItem;   // static array
{$ENDIF}

procedure InsertionSort(var A: TArray);
var
  I, J: Integer;
  Item: TItem;

begin
  for I:= 1 + Low(A) to High(A) do begin
    Item:= A[I];
    J:= I - 1;
    while (J >= Low(A)) and (A[J] > Item) do begin
      A[J + 1]:= A[J];
      Dec(J);
    end;
    A[J + 1]:= Item;
  end;
end;

var
  A: TArray;
  I: Integer;

begin
{$IFDEF DYNARRAY}
  SetLength(A, 16);
{$ENDIF}
  for I:= Low(A) to High(A) do
    A[I]:= Random(100);
  for I:= Low(A) to High(A) do
    Write(A[I]:3);
  Writeln;
  InsertionSort(A);
  for I:= Low(A) to High(A) do
    Write(A[I]:3);
  Writeln;
  Readln;
end.
Output:
  0  3 86 20 27 67 31 16 37 42  8 47  7 84  5 29
  0  3  5  7  8 16 20 27 29 31 37 42 47 67 84 86

String sort

// string is 1-based variable-length array of Char

procedure InsertionSort(var S: string);
var
  I, J, L: Integer;
  Ch: Char;

begin
  L:= Length(S);
  for I:= 2 to L do begin
    Ch:= S[I];
    J:= I - 1;
    while (J > 0) and (S[J] > Ch) do begin
      S[J + 1]:= S[J];
      Dec(J);
    end;
    S[J + 1]:= Ch;
  end;
end;
// in : S = 'the quick brown fox jumps over the lazy dog'
// out: S = '        abcdeeefghhijklmnoooopqrrsttuuvwxyz'

E

Some lines in this example are too long (more than 80 characters). Please fix the code if it's possible and remove this message.

A direct conversion of the pseudocode.

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

Test case:

? 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()

EasyLang

proc sort . d[] .
   for i = 2 to len d[]
      h = d[i]
      j = i - 1
      while j >= 1 and h < d[j]
         d[j + 1] = d[j]
         j -= 1
      .
      d[j + 1] = h
   .
.
data[] = [ 29 4 72 44 55 26 27 77 92 5 ]
sort data[]
print data[]

Eiffel

Works with: EiffelStudio version 6.6 (with provisional loop syntax)

This solution is shown in the routine sort of the class MY_SORTED_SET.

For a more complete explanation of the Eiffel sort examples, see the Bubble sort.

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

Elena

ELENA 6.x :

import extensions;
 
extension op
{
    insertionSort()
        = self.clone().insertionSort(0, self.Length - 1);
 
    insertionSort(int first, int last)
    {
        for(int i := first + 1; i <= last; i += 1)
        {
            var entry := self[i];
            int j := i;
 
            while (j > first && self[j - 1] > entry)
            {
                self[j] := self[j - 1];
 
                j -= 1
            };
 
            self[j] := entry
        }
    }
}
 
public program()
{
    var list := new int[]{3, 9, 4, 6, 8, 1, 7, 2, 5};
 
    console.printLine("before:", list.asEnumerable());
    console.printLine("after :", list.insertionSort().asEnumerable());
}
Output:
before:3,9,4,6,8,1,7,2,5
after :1,2,3,4,5,6,7,8,9

Elixir

defmodule Sort do
  def insert_sort(list) when is_list(list), do: insert_sort(list, [])
  
  def insert_sort([], sorted), do: sorted
  def insert_sort([h | t], sorted), do: insert_sort(t, insert(h, sorted))
  
  defp insert(x, []), do: [x]
  defp insert(x, sorted) when x < hd(sorted), do: [x | sorted]
  defp insert(x, [h | t]), do: [h | insert(x, t)]
end

Example:

iex(10)> Sort.insert_sort([5,3,9,4,1,6,8,2,7])
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Emacs Lisp

(defun min-or-max-of-a-list (numbers comparator)
  "Return minimum or maximum of NUMBERS using COMPARATOR."
  (let ((extremum (car numbers)))
    (dolist (n (cdr numbers))
      (when (funcall comparator n extremum)
        (setq extremum n)))
    extremum))

(defun remove-number-from-list (numbers n)
  "Return NUMBERS without N.
If n is present twice or more, it will be removed only once."
  (let (result)
    (while numbers
      (let ((number (pop numbers)))
        (if (= number n)
            (while numbers
              (push (pop numbers) result))
          (push number result))))
    (nreverse result)))

(defun insertion-sort (numbers comparator)
  "Return sorted list of NUMBERS using COMPARATOR."
  (if numbers
      (let ((extremum (min-or-max-of-a-list numbers comparator)))
        (cons extremum
	      (insertion-sort (remove-number-from-list numbers extremum)
                              comparator)))
    nil))

(insertion-sort '(1 2 3 9 8 7 25 12 3 2 1) #'>)
Output:
(25 12 9 8 7 3 3 2 2 1 1)

EMal

fun insertionSort = void by List a # sort list in place
  for int i = 1; i < a.length; ++i
    var v = a[i]
    int j
    for j = i - 1; j >= 0 and a[j] > v; --j
      a[j + 1] = a[j]
    end	
    a[j + 1] = v
  end
end
List lists = List[ # a list of lists
  int[4, 65, 2, -31, 0, 99, 83, 782, 1],
  real[5.17, 2, 5.12], 
  text["this", "is", "insertion", "sort"]]
for each List list in lists
  writeLine("Before: " + text!list) # list as text
  insertionSort(list)
  writeLine("After : " + text!list)
  writeLine()
end
Output:
Before: [4,65,2,-31,0,99,83,782,1]
After : [-31,0,1,2,4,65,83,99,782]

Before: [5.17,2.0,5.12]
After : [2.0,5.12,5.17]

Before: [this,is,insertion,sort]
After : [insertion,is,sort,this]

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)].

And the calls:

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]

ERRE

Note: array index is assumed to start at zero.

PROGRAM INSERTION_SORT

DIM A[9]

PROCEDURE INSERTION_SORT(A[])
    LOCAL I,J
    FOR I=0 TO UBOUND(A,1) DO
        V=A[I]
        J=I-1
        WHILE J>=0 DO
          IF A[J]>V THEN
            A[J+1]=A[J]
            J=J-1
           ELSE
            EXIT
          END IF
        END WHILE
        A[J+1]=V
    END FOR
END PROCEDURE

BEGIN
  A[]=(4,65,2,-31,0,99,2,83,782,1)
  FOR I%=0 TO UBOUND(A,1) DO
     PRINT(A[I%];)
  END FOR
  PRINT
  INSERTION_SORT(A[])
  FOR I%=0 TO UBOUND(A,1) DO
     PRINT(A[I%];)
  END FOR
  PRINT
END PROGRAM
Output:
 4  65  2 -31  0  99  2  83  782  1
-31  0  1  2  2  4  65  83  99  782

Euphoria

function insertion_sort(sequence s)
    object temp
    integer j
    for i = 2 to length(s) do
        temp = s[i]
        j = i-1
        while j >= 1 and compare(s[j],temp) > 0 do
            s[j+1] = s[j]
            j -= 1
        end while
        s[j+1] = temp
    end for
    return s
end function

include misc.e
constant s = {4, 15, "delta", 2, -31, 0, "alfa", 19, "gamma", 2, 13, "beta", 782, 1}

puts(1,"Before: ")
pretty_print(1,s,{2})
puts(1,"\nAfter: ")
pretty_print(1,insertion_sort(s),{2})
Output:
Before: {
  4,
  15,
  "delta",
  2,
  -31,
  0,
  "alfa",
  19,
  "gamma",
  2,
  13,
  "beta",
  782,
  1
}
After: {
  -31,
  0,
  1,
  2,
  2,
  4,
  13,
  15,
  19,
  782,
  "alfa",
  "beta",
  "delta",
  "gamma"
}

F#

Procedural Version

// This function performs an insertion sort with an array.
// The input parameter is a generic array (any type that can perform comparison).
// As is typical of functional programming style the input array is not modified;
// a copy of the input array is made and modified and returned.
let insertionSort (A: _ array) = 
    let B = Array.copy A
    for i = 1 to B.Length - 1 do
        let mutable value = B.[i]
        let mutable j = i - 1
        while (j >= 0 && B.[j] > value) do
            B.[j+1] <- B.[j]
            j <- j - 1
        B.[j+1] <- value
    B  // the array B is returned

Functional Version

let insertionSort collection = 

    // Inserts an element into its correct place in a sorted collection
    let rec sinsert element collection =
        match element, collection with
        | x, [] -> [x]
        | x, y::ys when x < y -> x::y::ys
        | x, y::ys -> y :: (ys |> sinsert x)

    // Performs Insertion Sort
    let rec isort acc collection = 
        match collection, acc with
        | [], _ -> acc
        | x::xs, ys -> xs |> isort (sinsert x ys)
    collection |> isort []

Factor

Translation of: Haskell
USING: kernel prettyprint sorting.extras sequences ;

: insertion-sort ( seq -- sorted-seq )
    <reversed> V{ } clone [ swap insort-left! ] reduce ;

{ 6 8 5 9 3 2 1 4 7 } insertion-sort .
Output:
{ 1 2 3 4 5 6 7 8 9 }

But note that Factor already comes with an insertion-sort in the sorting.insertion vocabulary that is likely faster and more robust. See its implementation here.

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

Works with: Fortran version 90 and later
subroutine sort(n, a)
    implicit none
    integer :: n, i, j
    real :: a(n), x
    
    do i = 2, n
        x = a(i)
        j = i - 1
        do while (j >= 1)
            if (a(j) <= x) exit
            a(j + 1) = a(j)
            j = j - 1
        end do
        a(j + 1) = x
    end do
end subroutine

Alternate Fortran 77 version

      SUBROUTINE SORT(N,A)
      IMPLICIT NONE
      INTEGER N,I,J
      DOUBLE PRECISION A(N),X
      DO 30 I = 2,N
        X = A(I)
        J = I
   10   J = J - 1
        IF (J.EQ.0) GO TO 20
        IF (A(J).LE.X) GO TO 20
        A(J + 1) = A(J)
        GO TO 10
   20   A(J + 1) = X
   30 CONTINUE
      END

FreeBASIC

' version 20-10-2016
' compile with: fbc -s console
' for boundry checks on array's compile with: fbc -s console -exx

Sub insertionSort( arr() As Long )

  ' sort from lower bound to the highter bound
  ' array's can have subscript range from -2147483648 to +2147483647

  Dim As Long lb = LBound(arr)
  Dim As Long i, j, value

  For i = lb +1 To UBound(arr)

    value = arr(i)
    j = i -1
    While j >= lb  And arr(j) > value
      arr(j +1) = arr(j)
      j = j -1
    Wend

    arr(j +1) = value

  Next

End Sub

' ------=< MAIN >=------

Dim As Long i, array(-7 To 7)
Dim As Long a = LBound(array), b = UBound(array)

Randomize Timer
For i = a To b : array(i) = i  : Next
For i = a To b ' little shuffle
  Swap array(i), array(Int(Rnd * (b - a +1)) + a)
Next

Print "unsort ";
For i = a To b : Print Using "####"; array(i); : Next : Print
insertionSort(array())  ' sort the array
Print "  sort ";
For i = a To b : Print Using "####"; array(i); : Next : Print


' empty keyboard buffer
While Inkey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End
Output:
unsort   -7  -1   4  -6   5   2   1  -2   0  -5  -4   6  -3   7   3
  sort   -7  -6  -5  -4  -3  -2  -1   0   1   2   3   4   5   6   7

GAP

InsertionSort := function(L) 
  local n, i, j, x;
  n := Length(L);
  for i in [ 2 .. n ] do
    x := L[i];
    j := i - 1;
    while j >= 1 and L[j] > x do
      L[j + 1] := L[j];
      j := j - 1;
    od;
    L[j + 1] := x;
  od;
end;

s := "BFKRIMPOQACNESWUTXDGLVZHYJ";
InsertionSort(s);
s;
# "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

Go

package main

import "fmt"

func insertionSort(a []int) {
    for i := 1; i < len(a); i++ {
        value := a[i]
        j := i - 1
        for j >= 0 && a[j] > value {
            a[j+1] = a[j]
            j = j - 1
        }
        a[j+1] = value
    }
}

func main() {
    list := []int{31, 41, 59, 26, 53, 58, 97, 93, 23, 84}
    fmt.Println("unsorted:", list)

    insertionSort(list)
    fmt.Println("sorted!  ", list)
}
Output:
unsorted: [31 41 59 26 53 58 97 93 23 84]
sorted!   [23 26 31 41 53 58 59 84 93 97]

A generic version that takes any container that conforms to sort.Interface:

package main

import (
  "fmt"
  "sort"
)

func insertionSort(a sort.Interface) {
    for i := 1; i < a.Len(); i++ {
        for j := i; j > 0 && a.Less(j, j-1); j-- {
            a.Swap(j-1, j)
        }
    }
}

func main() {
    list := []int{31, 41, 59, 26, 53, 58, 97, 93, 23, 84}
    fmt.Println("unsorted:", list)

    insertionSort(sort.IntSlice(list))
    fmt.Println("sorted!  ", list)
}
Output:
unsorted: [31 41 59 26 53 58 97 93 23 84]
sorted!   [23 26 31 41 53 58 59 84 93 97]

Using binary search to locate the place to insert:

package main

import (
  "fmt"
  "sort"
)

func insertionSort(a []int) {
    for i := 1; i < len(a); i++ {
        value := a[i]
        j := sort.Search(i, func(k int) bool { return a[k] > value })
        copy(a[j+1:i+1], a[j:i])
        a[j] = value
    }
}

func main() {
    list := []int{31, 41, 59, 26, 53, 58, 97, 93, 23, 84}
    fmt.Println("unsorted:", list)

    insertionSort(list)
    fmt.Println("sorted!  ", list)
}
Output:
unsorted: [31 41 59 26 53 58 97 93 23 84]
sorted!   [23 26 31 41 53 58 59 84 93 97]

Groovy

Solution:

def insertionSort = { list ->
    
    def size = list.size()
    (1..<size).each { i ->
        def value = list[i]
        def j = i - 1
        for (; j >= 0 && list[j] > value; j--) {
            print "."; list[j+1] = list[j]
        }
        print "."; list[j+1] = value
    }
    list
}

Test:

println (insertionSort([23,76,99,58,97,57,35,89,51,38,95,92,24,46,31,24,14,12,57,78,4]))
println (insertionSort([88,18,31,44,4,0,8,81,14,78,20,76,84,33,73,75,82,5,62,70,12,7,1]))
Output:
..................................................................................................................................................................[4, 12, 14, 23, 24, 24, 31, 35, 38, 46, 51, 57, 57, 58, 76, 78, 89, 92, 95, 97, 99]
...............................................................................................................................................................[0, 1, 4, 5, 7, 8, 12, 14, 18, 20, 31, 33, 44, 62, 70, 73, 75, 76, 78, 81, 82, 84, 88]

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]

Haxe

class InsertionSort {
  @:generic
  public static function sort<T>(arr:Array<T>) {
    for (i in 1...arr.length) {
      var value = arr[i];
      var j = i - 1;
      while (j >= 0 && Reflect.compare(arr[j], value) > 0) {
        arr[j + 1] = arr[j--];
      }
      arr[j + 1] = value;
    }
  }
}

class Main {
  static function main() {
    var integerArray = [1, 10, 2, 5, -1, 5, -19, 4, 23, 0];
    var floatArray = [1.0, -3.2, 5.2, 10.8, -5.7, 7.3, 
                      3.5, 0.0, -4.1, -9.5];
    var stringArray = ['We', 'hold', 'these', 'truths', 'to', 
                       'be', 'self-evident', 'that', 'all', 
                       'men', 'are', 'created', 'equal'];
    Sys.println('Unsorted Integers: ' + integerArray);
    InsertionSort.sort(integerArray);
    Sys.println('Sorted Integers:   ' + integerArray);
    Sys.println('Unsorted Floats:   ' + floatArray);
    InsertionSort.sort(floatArray);
    Sys.println('Sorted Floats:     ' + floatArray);
    Sys.println('Unsorted Strings:  ' + stringArray);
    InsertionSort.sort(stringArray);
    Sys.println('Sorted Strings:    ' + stringArray);
  }
}
Output:
Unsorted Integers: [1,10,2,5,-1,5,-19,4,23,0]
Sorted Integers:   [-19,-1,0,1,2,4,5,5,10,23]
Unsorted Floats:   [1,-3.2,5.2,10.8,-5.7,7.3,3.5,0,-4.1,-9.5]
Sorted Floats:     [-9.5,-5.7,-4.1,-3.2,0,1,3.5,5.2,7.3,10.8]
Unsorted Strings:  [We,hold,these,truths,to,be,self-evident,that,all,men,are,created,equal]
Sorted Strings:    [We,all,are,be,created,equal,hold,men,self-evident,that,these,to,truths]

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

Icon and Unicon

procedure main()                     #: demonstrate various ways to sort a list and string 
   demosort(insertionsort,[3, 14, 1, 5, 9, 2, 6, 3],"qwerty")
end

procedure insertionsort(X,op)        #: return sorted X
local i,temp 

   op := sortop(op,X)                # select how and what we sort
   
   every i := 2 to *X do {
      temp := X[j := i]
      while op(temp,X[1 <= (j -:= 1)]) do 
         X[j+1] := X[j]
      X[j+1] := temp
      }
   return X
end

Note: This example relies on the supporting procedures 'sortop', and 'demosort' in Bubble Sort. The full demosort exercises the named sort of a list with op = "numeric", "string", ">>" (lexically gt, descending),">" (numerically gt, descending), a custom comparator, and also a string.

abbreviated:
Sorting Demo using procedure insertionsort
  on list : [ 3 14 1 5 9 2 6 3 ]
    with op = &null:         [ 1 2 3 3 5 6 9 14 ]   (0 ms)
  ...
  on string : "qwerty"
    with op = &null:         "eqrtwy"   (0 ms)

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)

A shorter, but slightly less efficient, version:

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)

Isabelle

theory Insertionsort
  imports Main
begin

fun insert :: "int ⇒ int list ⇒ int list" where
  "insert x [] = [x]"
| "insert x (y#ys) = (if x ≤ y then (x#y#ys) else y#(insert x ys))"

text‹Example:›
lemma "insert 4 [1, 2, 3, 5, 6] = [1, 2, 3, 4, 5, 6]" by(code_simp)

fun insertionsort :: "int list ⇒ int list" where
  "insertionsort [] = []"
| "insertionsort (x#xs) = insert x (insertionsort xs)"

lemma "insertionsort [4, 2, 6, 1, 8, 1] = [1, 1, 2, 4, 6, 8]" by(code_simp)

text
Our function behaves the same as the \<^term>‹sort› function of the standard library.

lemma insertionsort: "insertionsort xs = sort xs"
proof(induction xs)
  case Nil
  show "insertionsort [] = sort []" by simp
next
  case (Cons x xs)
  text‹Our \<^const>‹insert› behaves the same as the std libs \<^const>‹insort›.›
  have "insert a as = insort a as" for a as by(induction as) simp+
  with Cons show "insertionsort (x # xs) = sort (x # xs)" by simp
qed

text
Given that we behave the same as the std libs sorting algorithm,
we get the correctness properties for free.

corollary insertionsort_correctness:
  "sorted (insertionsort xs)" and
  "set (insertionsort xs) = set xs"
  using insertionsort by(simp)+

text
The Haskell implementation from
🌐‹https://rosettacode.org/wiki/Sorting_algorithms/Insertion_sort#Haskell›
also behaves the same. Ultimately, they all return a sorted list.
One exception to the Haskell implementation is that the type signature of
\<^const>‹foldr› in Isabelle is slightly different:
The initial value of the accumulator goes last.

definition rosettacode_haskell_insertionsort :: "int list ⇒ int list" where
  "rosettacode_haskell_insertionsort ≡ λxs. foldr insert xs []"

lemma "rosettacode_haskell_insertionsort [4, 2, 6, 1, 8, 1] =
       [1, 1, 2, 4, 6, 8]" by(code_simp)

lemma "rosettacode_haskell_insertionsort xs = insertionsort xs"
  unfolding rosettacode_haskell_insertionsort_def by(induction xs) simp+

end


J

Generally, this task should be accomplished in J using /:~. Here we take an approach that's more comparable with the other examples on this page.

Solution inspired by the Common LISP solution:

isort=:((>: # ]) , [ , < #])/

Example of use:

   isort 32 4 1 34 95 3 2 120 _38
_38 1 2 3 4 32 34 95 120

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

Using some built-in algorithms (warning: not stable, due to the lack of an "upper bound" binary search function)

Translation of: C++
public static <E extends Comparable<? super E>> void insertionSort(List<E> a) {
  for (int i = 1; i < a.size(); i++) {
    int j = Math.abs(Collections.binarySearch(a.subList(0, i), a.get(i)) + 1);
    Collections.rotate(a.subList(j, i+1), j - i);
  }
}
public static <E extends Comparable<? super E>> void insertionSort(E[] a) {
  for (int i = 1; i < a.length; i++) {
    E x = a[i];
    int j = Math.abs(Arrays.binarySearch(a, 0, i, x) + 1);
    System.arraycopy(a, j, a, j+1, i-j);
    a[j] = x;
  }
}

JavaScript

function insertionSort (a) {
    for (var i = 0; i < a.length; i++) {
        var k = a[i];
        for (var j = i; j > 0 && k < a[j - 1]; j--)
            a[j] = a[j - 1];
        a[j] = k;
    }
    return a;
}

var a = [4, 65, 2, -31, 0, 99, 83, 782, 1];
insertionSort(a);
document.write(a.join(" "));

jq

Works with: jq version 1.4

The insertion sort can be expressed directly in jq as follows:

def insertion_sort:
  reduce .[] as $x ([]; insert($x));

where insert/1 inserts its argument into its input, which can, by construction, be assumed here to be sorted. This algorithm will work in jq for any JSON array.

The following solution uses an "industrial strength" implementation of bsearch (binary search) that requires the following control structure:

# As soon as "condition" is true, then emit . and stop:
def do_until(condition; next):
  def u: if condition then . else (next|u) end;
  u;

bsearch is the only non-trivial part of this solution, and so we include its complete specification:

Assuming the input array is sorted, bsearch/1 returns the index of the target if the target is in the input array; and otherwise (-1 - ix), where ix is the insertion point that would leave the array sorted.

If the input is not sorted, bsearch will terminate but with irrelevant results.

def bsearch(target):
  if length == 0 then -1
  elif length == 1 then
     if target == .[0] then 0 elif target < .[0] then -1 else -2 end
  else . as $in
    # state variable: [start, end, answer]
    # where start and end are the upper and lower offsets to use.
      | [0, length-1, null]
      | do_until( .[0] > .[1] ;
                (if .[2] != null then (.[1] = -1) # i.e. break
                 else
                   ( ( (.[1] + .[0]) / 2 ) | floor ) as $mid
                 | $in[$mid] as $monkey
                 | if $monkey == target  then (.[2] = $mid)     # success
                   elif .[0] == .[1]     then (.[1] = -1)       # failure
                   elif $monkey < target then (.[0] = ($mid + 1))
                   else (.[1] = ($mid - 1))
                   end
                 end ))
    | if .[2] == null then # compute the insertion point
         if $in[ .[0] ] < target then (-2 -.[0]) 
         else (-1 -.[0])
         end
      else .[2]
      end
  end;

# insert x assuming input is sorted
def insert(x):
  if length == 0 then [x]
  else
    bsearch(x) as $i 
    | ( if $i < 0 then -(1+$i) else $i end ) as $i
    | .[0:$i] + [x] + .[$i:]
  end ;

def insertion_sort:
   reduce .[] as $x ([]; insert($x));

Example:

[1, 2, 1, 1.1, -1.1, null, [null], {"null":null}] | insertion_sort
Output:
[null,-1.1,1,1,1.1,2,[null],{"null":null}]

Julia

# v0.6

function insertionsort!(A::Array{T}) where T <: Number
    for i in 1:length(A)-1
        value = A[i+1]
        j = i
        while j > 0 && A[j] > value
            A[j+1] = A[j]
            j -= 1
        end
        A[j+1] = value
    end
    return A
end

x = randn(5)
@show x insertionsort!(x)
Output:
x = [-1.24011, -1.23848, 0.176698, -1.01986, 0.830544]
insertionsort!(x) = [-1.24011, -1.23848, -1.01986, 0.176698, 0.830544]

Kotlin

Standard solution, using int array

fun insertionSort(array: IntArray) {
    for (index in 1 until array.size) {
        val value = array[index]
        var subIndex = index - 1
        while (subIndex >= 0 && array[subIndex] > value) {
            array[subIndex + 1] = array[subIndex]
            subIndex--
        }
        array[subIndex + 1] = value
    }
}

fun main(args: Array<String>) {
    val numbers = intArrayOf(5, 2, 3, 17, 12, 1, 8, 3, 4, 9, 7)

    fun printArray(message: String, array: IntArray) = with(array) {
        print("$message [")
        forEachIndexed { index, number ->
            print(if (index == lastIndex) number else "$number, ")
        }
        println("]")
    }

    printArray("Unsorted:", numbers)
    insertionSort(numbers)
    printArray("Sorted:", numbers)
}
Output:
Unsorted: [5, 2, 3, 17, 12, 1, 8, 3, 4, 9, 7]
Sorted:   [1, 2, 3, 3, 4, 5, 7, 8, 9, 12, 17]

Alternative solution, optimized using binary search

Similar concept to C++ solution. This solution uses a hand-written algorithm to find the upper bound as there is no Kotlin/Java equivalent to C++'s `std::upper_bound`. Thus this function performs a stable sort (unlike the Java solution which uses `binarySearch`). It uses `copyInto` which is a faster way of shifting the elements of an array before inserting an element, compared to assigning individual array elements in a loop.

fun <T : Comparable<T>> Array<T>.insertionSort() {
    for (i in 1..lastIndex) {
        val currentElement = this[i]
        var low = 0
        var high = i - 1
        while (low <= high) {
            val mid = low + (high - low) / 2
            if (this[mid] <= currentElement)
                low = mid + 1
            else
                high = mid - 1
        }
        copyInto(this, low + 1, low, i)
        this[low] = currentElement
    }
}

Ksh

#!/bin/ksh

# An insertion sort in ksh

#	# Variables:
#
typeset -a arr=( 4 65 2 -31 0 99 2 83 782 1 )

#	# Functions:
#

#	# Function _insertionSort(array) - Insersion sort of array of integers
#
function _insertionSort {
	typeset _arr ; nameref _arr="$1"
	typeset _i _j _val ; integer _i _j _val

    for (( _i=1; _i<${#_arr[*]}; _i++ )); do
        _val=${_arr[_i]}
        (( _j = _i - 1 ))
        while (( _j>=0 && _arr[_j]>_val )); do
            _arr[_j+1]=${_arr[_j]}
            (( _j-- ))
        done
        _arr[_j+1]=${_val}
    done
}

 ######
# main #
 ######

_insertionSort arr

printf "%s" "( "
for (( i=0; i<${#arr[*]}; i++ )); do
	printf "%d " ${arr[i]}
done
printf "%s\n" " )"
Output:

( -31 0 1 2 2 4 65 83 99 782 )

Lambdatalk

{def sort

 {def sort.i
  {lambda {:x :a}
   {if {A.empty? :a}
    then {A.new :x}
    else {if {<= :x {A.first :a}}
    then {A.addfirst! :x :a}
    else {A.addfirst! {A.first :a} {sort.i :x {A.rest :a}}} }}}}

 {def sort.r
  {lambda {:a1 :a2}
   {if {A.empty? :a1}
    then :a2 
    else {sort.r {A.rest :a1} {sort.i {A.first :a1} :a2}} }}}

 {lambda {:a}
  {sort.r :a {A.new}} }}
-> sort

{def A {A.new 4 65 2 -31 0 99 83 782 1}}
-> A

{sort {A}}
-> [-31,0,1,2,4,65,83,99,782]

Liberty BASIC

   itemCount = 20
    dim A(itemCount)
    for i = 1 to itemCount
        A(i) = int(rnd(1) * 100)
    next i

    print "Before Sort"
    gosub [printArray]

'--- Insertion sort algorithm
    for i = 2 to itemCount
        value = A(i)
        j = i-1
        while j >= 0 and A(j) > value
            A(j+1) = A(j)
            j = j-1
        wend
        A(j+1) = value
    next
'--- end of (Insertion sort algorithm)

    print "After Sort"
    gosub [printArray]
end

[printArray]
    for i = 1 to itemCount
        print using("###", A(i));
    next i
    print
return

Lua

Binary variation of Insertion sort (Has better complexity)

do
	local function lower_bound(container, container_begin, container_end, value, comparator)
		local count = container_end - container_begin + 1

		while count > 0 do
			local half = bit.rshift(count, 1) -- or math.floor(count / 2)
			local middle = container_begin + half

			if comparator(container[middle], value) then
				container_begin = middle + 1
				count = count - half - 1
			else
				count = half
			end
		end

		return container_begin
	end

	local function binary_insertion_sort_impl(container, comparator)
		for i = 2, #container do
			local j = i - 1
			local selected = container[i]
			local loc = lower_bound(container, 1, j, selected, comparator)

			while j >= loc do
				container[j + 1] = container[j]
				j = j - 1
			end

			container[j + 1] = selected
		end
	end

	local function binary_insertion_sort_comparator(a, b)
		return a < b
	end

	function table.bininsertionsort(container, comparator)
		if not comparator then
			comparator = binary_insertion_sort_comparator
		end

		binary_insertion_sort_impl(container, comparator)
	end
end
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}))

Maple

arr := Array([17,3,72,0,36,2,3,8,40,0]):
len := numelems(arr):
for i from 2 to len do
	val := arr[i]:
	j := i-1:
	while(j > 0 and arr[j] > val) do
		arr[j+1] := arr[j]:
		j--:
	end do:
	arr[j+1] := val:
end do:
arr;
Output:
[0,0,2,3,3,8,17,36,40,72]

Mathematica/Wolfram Language

insertionSort[a_List] := Module[{A = a},
  For[i = 2, i <= Length[A], i++,
   value = A[[i]];    j = i - 1;
   While[j >= 1 && A[[j]] > value, A[[j + 1]] = A[[j]]; j--;];
   A[[j + 1]] = value;]; 
A
]
Output:
insertionSort@{ 2, 1, 3, 5}
{1, 2, 3, 5}

MATLAB / Octave

This is a direct translation of the pseudo-code above, except that it has been modified to compensate for MATLAB's 1 based arrays.

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

Sample Usage:

>> insertionSort([4 3 1 5 6 2])

ans =

     1     2     3     4     5     6

Maxima

insertion_sort(u) := block(
   [n: length(u), x, j],
   for i from 2 thru n do (
      x: u[i],
      j: i - 1,
      while j >= 1 and u[j] > x do (
         u[j + 1]: u[j],
         j: j - 1      
      ),
      u[j + 1]: x
   )
)$

MAXScript

fn inSort arr =
(
	arr = deepcopy arr
	for i = 1 to arr.count do
	(
		j = i
		while j > 1 and arr[j-1] > arr[j] do
		(
			swap arr[j] arr[j-1]
			j -= 1
		)
	)
	return arr
)

Output:

b = for i in 1 to 20 collect random 1 40
#(2, 28, 35, 31, 27, 24, 2, 22, 15, 34, 9, 10, 22, 40, 26, 5, 23, 6, 18, 33)
a = insort b
#(2, 2, 5, 6, 9, 10, 15, 18, 22, 22, 23, 24, 26, 27, 28, 31, 33, 34, 35, 40)

Miranda

main :: [sys_message]
main = [Stdout ("Before: " ++ show testlist ++ "\n"),
        Stdout ("After:  " ++ show (insertionsort testlist) ++ "\n")]
       where testlist = [4,65,2,-31,0,99,2,83,782,1]


insertionsort :: [*]->[*]
insertionsort = foldr insert []

insert :: *->[*]->[*]
insert x []     = [x]
insert x (y:ys) = x:y:ys,        if x<y
                = y:insert x ys, otherwise
Output:
Before: [4,65,2,-31,0,99,2,83,782,1]
After:  [-31,0,1,2,2,4,65,83,99,782]

ML

mLite

Translation of: OCaml
fun insertion_sort L =
	let 
		fun insert
				(x,[]) = [x]
			|	(x, y :: ys) = 
					if x <= y then
						x :: y :: ys
					else
						y :: insert (x, ys)
	in
		foldr (insert,[]) L
	end;

println ` insertion_sort [6,8,5,9,3,2,1,4,7];

Output

[1, 2, 3, 4, 5, 6, 7, 8, 9]

Standard ML

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

Modula-3

Translation of: Ada
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.

N/t/roff

Works with: GNU Troff version 1.22.2

Sliding method

.de end
..
.de array
.	nr \\$1.c 0 1
.	de \\$1.push end
.		nr \\$1..\\\\n+[\\$1.c] \\\\$1
.	end
.	de \\$1.pushln end
.		if \\\\n(.$>0 .\\$1.push \\\\$1
.		if \\\\n(.$>1 \{ \
.			shift
.			\\$1.pushln \\\\$@
.		\}
.	end
.	de \\$1.dump end
.		nr i 0 1
.		ds out "
.		while \\\\n+i<=\\\\n[\\$1.c] .as out "\\\\n[\\$1..\\\\ni] 
.		tm \\\\*[out]
.		rm out
.		rr i
.	end
.	de \\$1.slideright end
.		nr i \\\\$1
.		nr i+1 \\\\ni+1
.		nr \\$1..\\\\n[i+1] \\\\n[\\$1..\\\\ni]
.		rr i
.		rr i+1
.	end
..
.de insertionsort
.	nr keyidx 1 1
.	while \\n+[keyidx]<=\\n[\\$1.c] \{ \
.		nr key \\n[\\$1..\\n[keyidx]]
.		nr compidx \\n[keyidx] 1
.		while \\n-[compidx]>=0 \{ \
.			if \\n[compidx]=0 \{ \
.				nr \\$1..1 \\n[key]
.				break
.			\}
.			ie \\n[\\$1..\\n[compidx]]>\\n[key] \{ \
.				\\$1.slideright \\n[compidx]
.			\}
.			el \{ \
.				nr compidx+1 \\n[compidx]+1
.				nr \\$1..\\n[compidx+1] \\n[key]
.				break
.			\}
.		\}
.	\}
..
.array a
.a.pushln 13 64 22 87 54 87 23 92 11 64 5 9 3 3 0
.insertionsort a
.a.dump

Swapping method

.de end
..
.de array
.	nr \\$1.c 0 1
.	de \\$1.push end
.		nr \\$1..\\\\n+[\\$1.c] \\\\$1
.	end
.	de \\$1.pushln end
.		if \\\\n(.$>0 .\\$1.push \\\\$1
.		if \\\\n(.$>1 \{ \
.			shift
.			\\$1.pushln \\\\$@
.		\}
.	end
.	de \\$1.dump end
.		nr i 0 1
.		ds out "
.		while \\\\n+i<=\\\\n[\\$1.c] .as out "\\\\n[\\$1..\\\\ni] 
.		tm \\\\*[out]
.		rm out
.		rr i
.	end
.	de \\$1.swap end
.		if (\\\\$1<=\\\\n[\\$1.c])&(\\\\$1<=\\\\n[\\$1.c]) \{ \
.			nr tmp \\\\n[\\$1..\\\\$2]
.			nr \\$1..\\\\$2 \\\\n[\\$1..\\\\$1]
.			nr \\$1..\\\\$1 \\\\n[tmp]
.			rr tmp
.		\}
.	end
..
.de insertionsort
.	nr keyidx 1 1
.	while \\n+[keyidx]<=\\n[\\$1.c] \{ \
.		nr compidx \\n[keyidx]+1 1
.		nr compidx-1 \\n[keyidx] 1
.		while (\\n-[compidx]>0)&(\\n[\\$1..\\n-[compidx-1]]>\\n[\\$1..\\n[compidx]]) \{ \
.			\\$1.swap \\n[compidx] \\n[compidx-1]
.		\}
.	\}
..
.array a
.a.pushln 13 64 22 87 54 87 23 92 11 64 5 9 3 3 0
.insertionsort a
.a.dump

Nanoquery

Translation of: Python
def insertion_sort(L)
	for i in range(1, len(L) - 1)
		j = i - 1
		key = L[i]
		while (L[j] > key) and (j >= 0)
			L[j + 1] = L[j]
			j -= 1
		end
		L[j+1] = key
	end

	return L
end

Nemerle

From the psuedocode.

using System.Console;
using Nemerle.English;

module InsertSort
{
    public static Sort(this a : array[int]) : void
    {
        mutable value = 0; mutable j = 0;
        foreach (i in [1 .. (a.Length - 1)])
        {
            value = a[i]; j = i - 1;
            while (j >= 0 and a[j] > value)
            {
                a[j + 1] = a[j];
                j = j - 1;
            }
            a[j + 1] = value;
        }
    }
    
    Main() : void
    {
        def arr = array[1, 4, 8, 3, 8, 3, 5, 2, 6];
        arr.Sort();
        foreach (i in arr) Write($"$i  ");
    }
}

NetRexx

/* NetRexx */
options replace format comments java crossref savelog symbols binary

import java.util.List

placesList = [String -
    "UK  London",     "US  New York",   "US  Boston",     "US  Washington" -
  , "UK  Washington", "US  Birmingham", "UK  Birmingham", "UK  Boston"     -
]

lists = [ -
    placesList -
  , insertionSort(String[] Arrays.copyOf(placesList, placesList.length)) -
]

loop ln = 0 to lists.length - 1
  cl = lists[ln]
  loop ct = 0 to cl.length - 1
    say cl[ct]
    end ct
    say
  end ln

return

method insertionSort(A = String[]) public constant binary returns String[]

  rl = String[A.length]
  al = List insertionSort(Arrays.asList(A))
  al.toArray(rl)

  return rl

method insertionSort(A = List) public constant binary returns ArrayList

  loop i_ = 1 to A.size - 1
    value = A.get(i_)
    j_ = i_ - 1
    loop label j_ while j_ >= 0
      if (Comparable A.get(j_)).compareTo(Comparable value) <= 0 then leave j_
      A.set(j_ + 1, A.get(j_))
      j_ = j_ - 1
      end j_
      A.set(j_ + 1, value)
    end i_

  return ArrayList(A)
Output:
UK  London
US  New York
US  Boston
US  Washington
UK  Washington
US  Birmingham
UK  Birmingham
UK  Boston

UK  Birmingham
UK  Boston
UK  London
UK  Washington
US  Birmingham
US  Boston
US  New York
US  Washington

Nim

proc insertSort[T](a: var openarray[T]) =
  for i in 1 .. a.high:
    let value = a[i]
    var j = i
    while j > 0 and value < a[j-1]:
      a[j] = a[j-1]
      dec j
    a[j] = value

var a = @[4, 65, 2, -31, 0, 99, 2, 83, 782]
insertSort a
echo a
Output:
@[-31, 0, 2, 2, 4, 65, 83, 99, 782]

Oberon-2

Translation of: Modula-3
MODULE InsertionSort;

  IMPORT Out;
    
  VAR
    A1:ARRAY 10 OF INTEGER;
    
  PROCEDURE Init;
  BEGIN
    A1[0] := 4; A1[1] := 65; A1[2] := 2; A1[3] := -31;
    A1[4] := 0; A1[5] := 99; A1[6] := 2; A1[7] := 83;
    A1[8] := 782; A1[9] := 1;
  END Init;
  
  PROCEDURE InsertionSort(VAR A:ARRAY OF INTEGER);
    VAR
      i,j:LONGINT;
      value:INTEGER;
  BEGIN
    FOR i := 1 TO LEN(A)-1 DO
      value := A[i];
      j := i-1;
      WHILE((j >= 0) & (A[j] > value)) DO A[j+1] := A[j]; DEC(j) END;
      A[j+1] := value
    END;
  END InsertionSort;

  PROCEDURE PrintArray(VAR A:ARRAY OF INTEGER);
    VAR i:LONGINT;
  BEGIN
    FOR i := 0 TO LEN(A)-1 DO Out.Int(A[i],0); Out.Char(' ') END;
    Out.Ln
  END PrintArray;
  
BEGIN
  Init;
  PrintArray(A1);
  InsertionSort(A1);
  PrintArray(A1);
END InsertionSort.
Output:
4 65 2 -31 0 99 2 83 782 1 
-31 0 1 2 2 4 65 83 99 782 

Objeck

bundle Default {
  class Insert {
    function : Main(args : String[]) ~ Nil {
      values := [9, 7, 10, 2, 9, 7, 4, 3, 10, 2, 7, 10];
      InsertionSort(values);
      each(i : values) {
        values[i]->PrintLine();
      };
    }
      
    function : InsertionSort (a : Int[]) ~ Nil {
      each(i : a) {
        value := a[i];
        j := i - 1;
        while(j >= 0 & a[j] > value) {
          a[j + 1] := a[j];
          j -= 1;
        };
        a[j + 1] := value;
      };
    }
  }
}

OCaml

let rec insert lst x =
  match lst with
  | y :: ys when x > y -> y :: insert ys x
  | _ -> x :: lst

let insertion_sort = List.fold_left insert []

let () = [6; 8; 5; 9; 3; 2; 1; 4; 7]
  |> insertion_sort |> List.iter (Printf.printf " %u") |> print_newline
Output:
 1 2 3 4 5 6 7 8 9

Oforth

Returns a new sorted list.

: insertionSort(a)
| l i j v |
   a asListBuffer ->l
   2 l size for: i [
      l at(i) ->v
      i 1- ->j
      while(j) [ 
         l at(j) dup v <= ifTrue: [ drop break ]
         j 1+ swap l put
         j 1- ->j
         ]
      l put(j 1 +, v)
      ]
   l ;
Output:
>[ 4, 65, 2, -31, 0, 99, 2, 83, 782, 1 ] insertionSort .
[-31, 0, 1, 2, 2, 4, 65, 83, 99, 782] ok
>

ooRexx

Translation of: REXX
/* REXX program sorts a stemmed array (has characters)                */
/* using the insertion sort algorithm                                 */
  Call gen                          /* fill the array with test data  */
  Call show 'before sort'           /* display the elements           */
  Say copies('-',79)                /* display a separator line       */
  Call insertionSort x.0            /* invoke the insertion sort.     */
  Call show ' after sort'           /* display the elements after sort*/
  Exit
/*--------------------------------------------------------------------*/
gen: Procedure Expose x.
  x.1="---Monday's Child Is Fair of Face  (by Mother Goose)---"
  x.2="======================================================="
  x.3="Monday's child is fair of face;"
  x.4="Tuesday's child is full of grace;"
  x.5="Wednesday's child is full of woe;"
  x.6="Thursday's child has far to go;"
  x.7="Friday's child is loving and giving;"
  x.8="Saturday's child works hard for a living;"
  x.9="But the child that is born on the Sabbath day"
  x.10="Is blithe and bonny, good and gay."
  x.0=10                            /* number of elements             */
  Return
/*--------------------------------------------------------------------*/
insertionsort: Procedure Expose x.
  Parse Arg n
  Do i=2 To n
    y=x.i
    Do j=i-1 By -1 To 1 While x.j>y
      z=j+1
      x.z=x.j
      /* Say 'set x.'z 'to x.'j '('||x.j||')' */
      End
    z=j+1
    x.z=y
    /* Say 'set x.'z 'to' y                   */
    End
  Return
/*--------------------------------------------------------------------*/
show:
  Do j=1 To x.0
    Say 'Element' right(j,length(x.0)) arg(1)":" x.j
    End
  Return
Output:
Element  1 before sort: ---Monday's Child Is Fair of Face  (by Mother Goose)---
Element  2 before sort: =======================================================
Element  3 before sort: Monday's child is fair of face;
Element  4 before sort: Tuesday's child is full of grace;
Element  5 before sort: Wednesday's child is full of woe;
Element  6 before sort: Thursday's child has far to go;
Element  7 before sort: Friday's child is loving and giving;
Element  8 before sort: Saturday's child works hard for a living;
Element  9 before sort: But the child that is born on the Sabbath day
Element 10 before sort: Is blithe and bonny, good and gay.
-------------------------------------------------------------------------------
Element  1  after sort: ---Monday's Child Is Fair of Face  (by Mother Goose)---
Element  2  after sort: =======================================================
Element  3  after sort: But the child that is born on the Sabbath day
Element  4  after sort: Friday's child is loving and giving;
Element  5  after sort: Is blithe and bonny, good and gay.
Element  6  after sort: Monday's child is fair of face;
Element  7  after sort: Saturday's child works hard for a living;
Element  8  after sort: Thursday's child has far to go;
Element  9  after sort: Tuesday's child is full of grace;
Element 10  after sort: Wednesday's child is full of woe;

Oz

Direct translation of pseudocode. In-place sorting of mutable arrays.

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

PARI/GP

insertionSort(v)={
  for(i=1,#v-1,
    my(j=i-1,x=v[i]);
    while(j && v[j]>x,
      v[j+1]=v[j];
      j--
    );
    v[j+1]=x
  );
  v
};

Pascal

Works with: FPC
program SortDemo;

{$mode objfpc}{$h+}{$b-}

procedure InsertionSort(var A: array of Integer);
var
  I, J, Tmp: Integer;
begin
  for I := 1 to High(a) do
    if A[I] < A[I - 1] then begin
      J := I;
      Tmp := A[I];
      repeat
        A[J] := A[J - 1];
        Dec(J);
      until (J = 0) or (Tmp >= A[J - 1]);
      A[J] := Tmp;
    end;
end;

procedure PrintArray(const A: array of Integer);
var
  I: Integer;
begin
  Write('[');
  for I := 0 to High(A) - 1 do
    Write(A[I], ', ');
  WriteLn(A[High(A)], ']');
end;

var
  a: array[-7..6] of Integer = (-34, -20, 30, 13, 36, -10, 5, -25, 9, 19, 35, -50, 29, 11);

begin
  InsertionSort(a);
  PrintArray(a);
end.
Output:
[-50, -34, -25, -20, -10, 5, 9, 11, 13, 19, 29, 30, 35, 36]

Perl

sub insertion_sort {
    my (@list) = @_;
    foreach my $i (1 .. $#list) {
        my $j = $i;
        my $k = $list[$i];
        while ( $j > 0 && $k < $list[$j - 1]) {
            $list[$j] = $list[$j - 1];
            $j--;
        }
        $list[$j] = $k;
    }
    return @list;
}

my @a = insertion_sort(4, 65, 2, -31, 0, 99, 83, 782, 1);
print "@a\n";
Output:
-31 0 1 2 4 65 83 99 782

Phix

Copy of Euphoria

function insertion_sort(sequence s)
object temp
integer j
    for i=2 to length(s) do
        temp = s[i]
        j = i-1
        while j>=1 and s[j]>temp do
            s[j+1] = s[j]
            j -= 1
        end while
        s[j+1] = temp
    end for
    return s
end function
 
constant s = {4, 15, "delta", 2, -31, 0, "alpha", 19, "gamma", 2, 13, "beta", 782, 1}
 
puts(1,"Before: ")    ?s
puts(1,"After: ")     ?insertion_sort(s)
Output:
Before: {4,15,"delta",2,-31,0,"alpha",19,"gamma",2,13,"beta",782,1}
After: {-31,0,1,2,2,4,13,15,19,782,"alpha","beta","delta","gamma"}

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);
1,2,3,4,6,7,8,9

PicoLisp

(de insertionSort (Lst)
   (for (I (cdr Lst)  I  (cdr I))
      (for (J Lst  (n== J I)  (cdr J))
         (T (> (car J) (car I))
            (rot J (offset I J)) ) ) )
   Lst )
Output:
: (insertionSort (5 3 1 7 4 1 1 20))
-> (1 1 1 3 4 5 7 20)

PL/I

insert_sort: proc(array);
  dcl array(*)      fixed bin(31);
  dcl (i,j,tmp,h,l) fixed bin(31);

  l = lbound(array, 1);
  h = hbound(array, 1);

  do i = l + 1 to h;
    tmp = array(i);

    do j = i - 1 by -1 while(j > l - 1 & array(j) > tmp);
      array(j + 1) = array(j);
    end;

    array(j + 1) = tmp;
  end;
end insert_sort;

PL/M

100H:

/* INSERTION SORT ON 16-BIT INTEGERS */
INSERTION$SORT: PROCEDURE (AP, LEN);
    DECLARE (AP, LEN, I, J, V, A BASED AP) ADDRESS;
    DO I = 1 TO LEN-1;
        V = A(I);
        J = I;
        DO WHILE J > 0 AND A(J-1) > V;
            A(J) = A(J-1);
            J = J-1;
        END;
        A(J) = V;
    END;
END INSERTION$SORT;

/* CP/M CALLS AND FUNCTION TO PRINT INTEGERS */
BDOS: PROCEDURE (FN, ARG);
    DECLARE FN BYTE, ARG ADDRESS;
    GO TO 5;
END BDOS;

PRINT$NUMBER: PROCEDURE (N);
    DECLARE S (7) BYTE INITIAL ('..... $');
    DECLARE (N, P) ADDRESS, C BASED P BYTE;
    P = .S(5);
DIGIT:
    P = P-1;
    C = N MOD 10 + '0';
    N = N / 10;
    IF N > 0 THEN GO TO DIGIT;
    CALL BDOS(9, P);
END PRINT$NUMBER;

/* SORT AN ARRAY */
DECLARE NUMBERS (11) ADDRESS INITIAL (4, 65, 2, 31, 0, 99, 2, 8, 3, 782, 1);
CALL INSERTION$SORT(.NUMBERS, LENGTH(NUMBERS));

/* PRINT THE SORTED ARRAY */
DECLARE N BYTE;
DO N = 0 TO LAST(NUMBERS);
    CALL PRINT$NUMBER(NUMBERS(N));
END;

CALL BDOS(0,0);
EOF
Output:
0 1 2 2 3 4 8 31 65 99 782

PowerShell

Very similar to the PHP code.

function insertionSort($arr){
	for($i=0;$i -lt $arr.length;$i++){
		$val = $arr[$i]
		$j = $i-1
		while($j -ge 0 -and $arr[$j] -gt $val){
			$arr[$j+1] = $arr[$j]
			$j--
		}
		$arr[$j+1] = $val
	}
}
 
$arr = @(4,2,1,6,9,3,8,7)
insertionSort($arr)
$arr -join ","
Output:
1,2,3,4,6,7,8,9

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

Functional approach

Works with SWI-Prolog.
Insertion sort inserts elements of a list in a sorted list. So we can use foldl to sort a list.

% insertion sort
isort(L, LS) :-
	foldl(insert, [], L, LS).


% foldl(Pred, Init, List, R).
foldl(_Pred, Val, [], Val).
foldl(Pred, Val, [H | T], Res) :-
	call(Pred, Val, H, Val1),
	foldl(Pred, Val1, T, Res).

% insertion in a sorted list
insert([], N, [N]).

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

insert([H | T], N, [H|L1]) :-
	insert(T, N, L1).

Example use:

 ?- isort([2,23,42,3,10,1,34,5],L).
L = [1,2,3,5,10,23,34,42] 

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

Python

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

Using pythonic iterators:

def insertion_sort(L):
    for i, value in enumerate(L):
        for j in range(i - 1, -1, -1):
            if L[j] > value:
                L[j + 1] = L[j]
                L[j] = value

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:]

This is also built-in to the standard library:

import bisect
def insertion_sort_bin(seq):
    for i in range(1, len(seq)):
        bisect.insort(seq, seq.pop(i), 0, i)

Qi

Based on the scheme version.

(define insert
  X []     -> [X]
  X [Y|Ys] -> [X Y|Ys] where (<= X Y)
  X [Y|Ys] -> [Y|(insert X Ys)])

(define insertion-sort
  []     -> []
  [X|Xs] -> (insert X (insertion-sort Xs)))

(insertion-sort [6 8 5 9 3 2 1 4 7])

Quackery

[ [] swap witheach
    [ swap 2dup findwith
        [ over > ] [ ]
      nip stuff ] ]        is insertionsort ( [ --> [ )

R

Direct translation of pseudocode.

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

R has native vectorized operations which allow the following, more efficient implementation.

insertion_sort <- function(x) {
  for (j in 2:length(x)) {
    key <- x[j]
    bp <- which.max(x[1:j] > key)
    # 'bp' stands for breakpoint
    if (bp == 1) {
      if (key < ar[1]){
          x <- c(key, ar[-j])
      }
    }
    else {
      x <- x[-j]
      x <- c(ar[1:bp - 1], key, x[bp : (s-1)])
    }
  return(x)
  }
}

Racket

This implementation makes use of the pattern matching facilities in the Racket distribution.

#lang racket

(define (sort < l)
  (define (insert x ys)
    (match ys
      [(list) (list x)]
      [(cons y rst) (cond [(< x y) (cons x ys)]
                          [else (cons y (insert x rst))])]))
  (foldl insert '() l))

Raku

(formerly Perl 6)

sub insertion_sort ( @a is copy ) {
    for 1 .. @a.end -> $i {
        my $value = @a[$i];
        my $j;
        loop ( $j = $i-1; $j >= 0 and @a[$j] > $value; $j-- ) {
            @a[$j+1] = @a[$j];
        }
        @a[$j+1] = $value;
    }
    return @a;
}

my @data = 22, 7, 2, -5, 8, 4;
say 'input  = ' ~ @data;
say 'output = ' ~ @data.&insertion_sort;
Output:
input  = 22 7 2 -5 8 4
output = -5 2 4 7 8 22

Rascal

import List;

public list[int] insertionSort(a){
	for(i <- [0..size(a)-1]){
		v = a[i];
		j = i-1;
		while(j >= 0 && a[j] > v){
			a[j+1] = a[j];
			j -= 1;
                }
		a[j+1] = v;
        }
	return a;
}
Output:
rascal>rascal>insertionSort([4, 65, 2, -31, 0, 99, 83, 782, 1])
list[int]: [-31,0,1,2,4,65,83,99,782]

REALbasic

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

REBOL

; This program works with REBOL version R2 and R3, to make it work with Red 
; change the word func to function
insertion-sort: func [
	a [block!]
	/local i [integer!] j [integer!] n [integer!]
	value [integer! string! date!]
][ 
	i: 2
	n: length? a

	while [i <= n][
        	value: a/:i
		j: i
		while [ all [ 	1 < j
				value < a/(j - 1) ]][
			
	       		a/:j: a/(j - 1)
			j: j - 1
        	]
        	a/:j: value
		i: i + 1
	]
	a
]

probe insertion-sort [4 2 1 6 9 3 8 7]

probe insertion-sort [ "---Monday's Child Is Fair of Face (by Mother Goose)---"
  "Monday's child is fair of face;"
  "Tuesday's child is full of grace;"
  "Wednesday's child is full of woe;"
 "Thursday's child has far to go;"
  "Friday's child is loving and giving;"
  "Saturday's child works hard for a living;"
  "But the child that is born on the Sabbath day"
  "Is blithe and bonny, good and gay."]

; just by adding the date! type to the local variable value the same function can sort dates.
probe insertion-sort [12-Jan-2015 11-Jan-2015 11-Jan-2016 12-Jan-2014]
Output:
[1 2 3 4 6 7 8 9]
[{---Monday's Child Is Fair of Face (by Mother Goose)---} 
    "But the child that is born on the Sabbath day" 
    "Friday's child is loving and giving;" 
    "Is blithe and bonny, good and gay." 
    "Monday's child is fair of face;" 
    "Saturday's child works hard for a living;" 
    "Thursday's child has far to go;" 
    "Tuesday's child is full of grace;" 
    "Wednesday's child is full of woe;"
]
[12-Jan-2014 11-Jan-2015 12-Jan-2015 11-Jan-2016]

Refal

$ENTRY Go {
    , 7 6 5 9 8 4 3 1 2 0: e.Arr
    = <Prout e.Arr>
      <Prout <Sort e.Arr>>;
};

Sort {
    (e.S) = e.S;
    (e.S) s.I e.X = <Sort (<Insert s.I e.S>) e.X>;
    e.X = <Sort () e.X>;
};

Insert {
    s.N = s.N;
    s.N s.M e.X, <Compare s.N s.M>: {
        '+' = s.M <Insert s.N e.X>;
        s.C = s.N s.M e.X;
    };
};
Output:
7 6 5 9 8 4 3 1 2 0
0 1 2 3 4 5 6 7 8 9

REXX

/*REXX program sorts a stemmed array (has characters) using the insertion sort algorithm*/
call gen                                         /*generate the array's (data) elements.*/
call show           'before sort'                /*display the  before  array elements. */
     say copies('▒', 85)                         /*display a separator line  (a fence). */
call insertionSort  #                            /*invoke the  insertion  sort.         */
call show           ' after sort'                /*display the   after  array elements. */
exit                                             /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
gen: @.=;                 @.1  = "---Monday's Child Is Fair of Face  (by Mother Goose)---"
                          @.2  = "======================================================="
                          @.3  = "Monday's child is fair of face;"
                          @.4  = "Tuesday's child is full of grace;"
                          @.5  = "Wednesday's child is full of woe;"
                          @.6  = "Thursday's child has far to go;"
                          @.7  = "Friday's child is loving and giving;"
                          @.8  = "Saturday's child works hard for a living;"
                          @.9  = "But the child that is born on the Sabbath day"
                          @.10 = "Is blithe and bonny, good and gay."
            do #=1  while @.#\==''; end;  #= #-1 /*determine how many entries in @ array*/
     return                                      /* [↑]  adjust # for the DO loop index.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
insertionSort:  procedure expose @.;      parse arg #
                          do i=2  to #;   $= @.i;       do j=i-1  by -1  to 1  while @.j>$
                                                        _= j + 1;        @._= @.j
                                                        end   /*j*/
                          _= j + 1;       @._= $
                          end   /*i*/
                return
/*──────────────────────────────────────────────────────────────────────────────────────*/
show:  do j=1  for #;  say '   element'  right(j,length(#))  arg(1)": "  @.j; end;  return
output   when using the default internal data:
   element  1 before sort:  ---Monday's Child Is Fair of Face  (by Mother Goose)---
   element  2 before sort:  =======================================================
   element  3 before sort:  Monday's child is fair of face;
   element  4 before sort:  Tuesday's child is full of grace;
   element  5 before sort:  Wednesday's child is full of woe;
   element  6 before sort:  Thursday's child has far to go;
   element  7 before sort:  Friday's child is loving and giving;
   element  8 before sort:  Saturday's child works hard for a living;
   element  9 before sort:  But the child that is born on the Sabbath day
   element 10 before sort:  Is blithe and bonny, good and gay.
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
   element  1  after sort:  ---Monday's Child Is Fair of Face  (by Mother Goose)---
   element  2  after sort:  =======================================================
   element  3  after sort:  But the child that is born on the Sabbath day
   element  4  after sort:  Friday's child is loving and giving;
   element  5  after sort:  Is blithe and bonny, good and gay.
   element  6  after sort:  Monday's child is fair of face;
   element  7  after sort:  Saturday's child works hard for a living;
   element  8  after sort:  Thursday's child has far to go;
   element  9  after sort:  Tuesday's child is full of grace;
   element 10  after sort:  Wednesday's child is full of woe;

Ring

alist = [7,6,5,9,8,4,3,1,2,0]
see insertionsort(alist)

func insertionsort blist
     for i = 1 to len(blist)
         value = blist[i]
         j = i - 1
         while j >= 1 and blist[j] > value
               blist[j+1] = blist[j]
               j = j - 1
         end   
         blist[j+1] = value
      next
      return blist

RPL

In RPL, the condition while j > 0 and A[j] > value do needs to be fully assessed before performing the loop: an error would then occur when j will equal zero. This is why the loop condition has been encapsulated in a IFERR..THEN..END structure, which removes the need to test the value of j.

Works with: Halcyon Calc version 4.2.7
RPL code Comment
 ≪ 'A' STO
  2 A SIZE FOR ii 
     A ii GET 
     ii 1 -
     WHILE 
       IFERR DUP2 A SWAP GET < THEN 3 DROPN 0 END REPEAT
       'A' OVER GETI PUT
       1 - 
     END 
     'A' SWAP 1 + ROT PUT 
  NEXT 
  A 'A' PURGE
≫ 'ISORT' STO 
( [array] -- [array] ) 
for i from 2 to length[A] do // RPL arrays starts at 1
   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
Display result and delete global variable

Input:
[ 1 4 -1 0 3 7 4 8 20 -6 ] ISORT
Output:
1: [ -6 -1 0 1 3 4 4 7 8 20 ]

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]
p ary.insertionsort!
# => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Alternative version which doesn't swap elements but rather removes and inserts the value at the correct place:

class Array
  def insertionsort!
    1.upto(length - 1) do |i|
      value = delete_at i
      j = i - 1
      j -= 1 while j >= 0 && value < self[j]
      insert(j + 1, value)
    end
    self
  end
end

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

Run BASIC

dim insSort(100)
sortEnd = 0
global inSort
global sortEnd

' -- insert some random numbers --

for i = 1 to 20
  a = int(1000 * rnd(1))
  x = insertSort(a)
next i

' --- Print the Sorted Data -----

print "End Sort:";sortEnd                ' number sorted
for i = 1 to sortEnd
 print i;" ";insSort(i)                  ' location and sorted data
next i
wait

function insertSort(x)                   ' Insert Sort Function 
i = 1
while x > insSort(i) and i <= sortEnd
  i = i + 1
wend
for j = sortEnd to i step -1
   insSort(j + 1) = insSort(j)
next j
insSort(i) = x
sortEnd    = sortEnd + 1
end function
End Sort:20
1 124
2 248
3 263
4 279
5 390
6 431
7 458
8 480
9 543
10 556
11 567
12 619
13 625
........

Rust

fn insertion_sort<T: std::cmp::Ord>(arr: &mut [T]) {
    for i in 1..arr.len() {
        let mut j = i;
        while j > 0 && arr[j] < arr[j-1] {
            arr.swap(j, j-1);
            j = j-1;
        }
    }
}

SASL

Copied from SASL manual, Appendix II, answer (2)(a)

DEF
sort () = ()
sort (a : x) = insert a (sort x)
insert a () = a,
insert a (b : x) = a < b -> a : b : x
          b : insert a x
?

Scala

def insertSort[X](list: List[X])(implicit ord: Ordering[X]) = {
  def insert(list: List[X], value: X) = list.span(x => ord.lt(x, value)) match {
    case (lower, upper) => lower ::: value :: upper
  }
  list.foldLeft(List.empty[X])(insert)
}

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

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;

Original source: [1]

Sidef

class Array {
    method insertion_sort {
        { |i|
            var j = i-1
            var k = self[i]
            while ((j >= 0) && (k < self[j])) {
                self[j+1] = self[j]
                j--
            }
            self[j+1] = k
        } << 1..self.end
        return self
    }
}

var a = 10.of { 100.irand }
say a.insertion_sort

SNOBOL4

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

* sort array
	i = 1
loop1	value = A<i>
	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>; i = ?lt(i,aSize) i + 1	:s(while)
end

Stata

mata
void insertion_sort(real vector a) {
	real scalar i, j, n, x
	
	n = length(a)
	for (i=2; i<=n; i++) {
		x = a[i]
		for (j=i-1; j>=1; j--) {
			if (a[j] <= x) break
			a[j+1] = a[j]
		}
		a[j+1] = x
	}
}
end

Swift

Using generics.

func insertionSort<T:Comparable>(inout list:[T]) {
    for i in 1..<list.count {
        var j = i
        
        while j > 0 && list[j - 1] > list[j] {
           swap(&list[j], &list[j - 1])
            j--
        }
    }
}

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

TI-83 BASIC

Input into L1, run prgmSORTINS, output in L2.

:"INSERTION"
:L1→L2
:0→A
:Lbl L
:A+1→A
:A→B
:While B>0
:If L2(B)≤L2(B+1)
:Goto B
:L2(B)→C
:L2(B+1)→L2(B)
:C→L2(B+1)
:B-1→B
:End
:Lbl B
:If A<(dim(L2)-1)
:Goto L
:DelVar A
:DelVar B
:DelVar C
:Return

uBasic/4tH

PRINT "Insertion sort:"
  n = FUNC (_InitArray)
  PROC _ShowArray (n)
  PROC _Insertionsort (n)
  PROC _ShowArray (n)
PRINT
 
END


_Insertionsort PARAM (1)               ' Insertion sort
  LOCAL (3)

  FOR b@ = 1 TO a@-1
    c@ = @(b@)
    d@ = b@
    DO WHILE (d@>0) * (c@ < @(ABS(d@-1)))
        @(d@) = @(d@-1)
        d@ = d@ - 1
    LOOP
    @(d@) = c@
  NEXT
RETURN
 
 
_Swap PARAM(2)                         ' Swap two array elements
  PUSH @(a@)
  @(a@) = @(b@)
  @(b@) = POP()
RETURN
 
 
_InitArray                             ' Init example array
  PUSH 4, 65, 2, -31, 0, 99, 2, 83, 782, 1
 
  FOR i = 0 TO 9
    @(i) = POP()
  NEXT
 
RETURN (i)
 
 
_ShowArray PARAM (1)                   ' Show array subroutine
  FOR i = 0 TO a@-1
    PRINT @(i),
  NEXT
 
  PRINT
RETURN

UnixPipes

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

Ursala

#import nat

insort = ~&i&& @hNCtX ~&r->lx ^\~&rt nleq-~rlrSPrhlPrSCPTlrShlPNCTPQ@rhPlD

test program:

#cast %nL

example = insort <45,82,69,82,104,58,88,112,89,74>
Output:
<45,58,69,74,82,82,88,89,104,112>

Vala

Translation of: Nim
void insertion_sort(int[] array) {
  var count = 0;
  for (int i = 1; i < array.length; i++) {
    var val = array[i];
    var j = i;
    while (j > 0 && val < array[j - 1]) {
      array[j] = array[j - 1];
      j--;
    }
    array[j] = val;
  }
}

void main() {
  int[] array = {4, 65, 2, -31, 0, 99, 2, 83, 782};
  insertion_sort(array);
  foreach (int i in array)
    print("%d ", i);
}
Output:
-31 0 2 2 4 65 83 99 782

VBA

Translation of: Phix
Option Base 1
Private Function insertion_sort(s As Variant) As Variant
    Dim temp As Variant
    Dim j As Integer
    For i = 2 To UBound(s)
        temp = s(i)
        j = i - 1
        Do While s(j) > temp
            s(j + 1) = s(j)
            j = j - 1
            If j = 0 Then Exit Do
        Loop
        s(j + 1) = temp
    Next i
    insertion_sort = s
End Function
 
Public Sub main()
    s = [{4, 15, "delta", 2, -31, 0, "alpha", 19, "gamma", 2, 13, "beta", 782, 1}]
    Debug.Print "Before: ", Join(s, ", ")
    Debug.Print "After: ", Join(insertion_sort(s), "' ")
End Sub
Output:
Before:       4, 15, delta, 2, -31, 0, alpha, 19, gamma, 2, 13, beta, 782, 1
After:        -31' 0' 1' 2' 2' 4' 13' 15' 19' 782' alpha' beta' delta' gamma

VBScript

Translation of: REALbasic
Randomize
Dim n(9) 'nine is the upperbound.
         'since VBS arrays are 0-based, it will have 10 elements.
For L = 0 to 9
   n(L) = Int(Rnd * 32768)
Next

WScript.StdOut.Write "ORIGINAL : "
For L = 0 to 9
   WScript.StdOut.Write n(L) & ";"
Next

InsertionSort n

WScript.StdOut.Write vbCrLf & "  SORTED : "
For L = 0 to 9
   WScript.StdOut.Write n(L) & ";"
Next

'the function
Sub InsertionSort(theList)
   For insertionElementIndex = 1 To UBound(theList)
      insertionElement = theList(insertionElementIndex)
      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
Output:
ORIGINAL : 26699;2643;10249;31612;21346;19702;29799;31115;20413;5197;
  SORTED : 2643;5197;10249;19702;20413;21346;26699;29799;31115;31612;

V (Vlang)

fn insertion(mut arr []int) {
	for i in 1 .. arr.len {
		value := arr[i]
		mut j := i - 1
		for j >= 0 && arr[j] > value {
			arr[j + 1] = arr[j]
			j--
		}
		arr[j + 1] = value
	}
}

fn main() {
	mut arr := [4, 65, 2, -31, 0, 99, 2, 83, 782, 1]
	println('Input: ' + arr.str())
	insertion(mut arr)
	println('Output: ' + arr.str())
}
Output:
Input: [4, 65, 2, -31, 0, 99, 2, 83, 782, 1]
Output: [-31, 0, 1, 2, 2, 4, 65, 83, 99, 782]

Wren

var insertionSort = Fn.new { |a|
    for (i in 1..a.count-1) {
        var v = a[i]
        var j = i - 1
        while (j >= 0 && a[j] > v) {
            a[j+1] = a[j]
            j = j - 1
        }
        a[j+1] = v
    }
}

var array = [ [4, 65, 2, -31, 0, 99, 2, 83, 782, 1], [7, 5, 2, 6, 1, 4, 2, 6, 3] ]
for (a in array) {
    System.print("Before: %(a)")
    insertionSort.call(a)
    System.print("After : %(a)")
    System.print()
}
Output:
Before: [4, 65, 2, -31, 0, 99, 2, 83, 782, 1]
After : [-31, 0, 1, 2, 2, 4, 65, 83, 99, 782]

Before: [7, 5, 2, 6, 1, 4, 2, 6, 3]
After : [1, 2, 2, 3, 4, 5, 6, 6, 7]


Alternatively we can just call a library method.

Library: Wren-sort
import "./sort" for Sort

var array = [ [4, 65, 2, -31, 0, 99, 2, 83, 782, 1], [7, 5, 2, 6, 1, 4, 2, 6, 3] ]
for (a in array) {
    System.print("Before: %(a)")
    Sort.insertion(a)
    System.print("After : %(a)")
    System.print()
}
Output:
As above.

XPL0

code ChOut=8, IntOut=11;

proc InsertionSort(A, L);       \Sort array A of length L
int  A, L;
int  I, J, V;
[for I:= 1 to L-1 do
    [V:= A(I); 
    J:= I-1;
    while J>=0 and A(J)>V do
        [A(J+1):= A(J);
        J:= J-1;
        ];
    A(J+1):= V;
    ];
];

int A, I;
[A:= [3, 1, 4, 1, -5, 9, 2, 6, 5, 4];
InsertionSort(A, 10);
for I:= 0 to 10-1 do [IntOut(0, A(I));  ChOut(0, ^ )];
]
Output:
-5 1 1 2 3 4 4 5 6 9 


Yabasic

Translation of: FreeBASIC
sub InsertionSort (matriz())
    for i = 1 to arraysize(matriz(),1)
        valor = matriz(i)
        j = i - 1
        while (j >= 0) and (valor < matriz(j))
              matriz(j + 1) = matriz(j)
              j = j - 1
        wend
        matriz(j + 1) = valor
    next i
end sub

//--------------------------
dim array(10)
print "Antes de ordenar:"
for i = 1 to 10
    array(i) = int(ran(32768))
    print array(i), " ";
next i
print
print "\nDespues de ordenar:"

InsertionSort(array())

for i = 1 to 10
    print array(i), " ";
next i
print
end


Yorick

Based on pseudocode, except using 1-based arrays.

func insertionSort(&A) {
  for(i = 2; i <= numberof(A); i++) {
    value = A(i);
    j = i - 1;
    while(j >= 1 && A(j) > value) {
      A(j+1) = A(j);
      j--;
    }
    A(j+1) = value;
  }
}

zkl

fcn insertionSort(list){
   sink:=List();
   foreach x in (list){
      if(False==(n:=sink.filter1n('>(x)))) sink.append(x); // x>all items in sink
      else sink.insert(n,x);
   }
   sink.close();
}
insertionSort(T(4,65,2,-31,0,99,2,83,782,1)).println();
insertionSort("big fjords vex quick waltz nymph".split()).println();
Output:
L(-31,0,1,2,2,4,65,83,99,782)
L("big","fjords","nymph","quick","vex","waltz")