I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

# Sorting algorithms/Insertion sort

(Redirected from Insertion sort)
Sorting algorithms/Insertion sort
You are encouraged to solve this task according to the task description, using any language you may know.

Sorting Algorithm
This is a sorting algorithm.   It may be applied to a set of data in order to sort it.     For comparing various sorts, see compare sorts.   For other sorting algorithms,   see sorting algorithms,   or:

O(n logn) sorts

O(n log2n) sorts
Shell Sort

O(n2) sorts
Bubble sort | Cocktail sort | Cocktail sort with shifting bounds | Comb sort | Cycle sort | Gnome sort | Insertion sort | Selection sort | Strand sort

 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/2016INSSORT  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 jELOOPJ   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 iELOOPI   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 iELOOPXI  XPRNT  PG,L'PG            print buffer         L      R13,4(0,R13)       epilog          LM     R14,R12,12(R13)    "         XR     R15,R15            "         BR     R14                exitA  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                  variableN        DC     A((V-A)/L'A)       n=hbound(a)PG       DC     CL80' '            bufferXDEC     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/2016INSSORTS 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                exitA  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                  variableN    DC     A((V-A)/L'A)       n=hbound(a)PG   DC     CL80' '            bufferXDEC DS     CL12               for xdeco     YREGS                     symbolics for registers     END    INSSORTS`
Output:

Same as previous

## AArch64 Assembly

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              *//*********************************/.dataszMessSortOk:       .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,7TableNumber:     .quad   10,9,8,7,6,-5,4,3,2,1                 .equ NBELEMENTS, (. - TableNumber) / 8 /*********************************//* UnInitialized data            *//*********************************/.bsssZoneConv:       .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 100f1:                                                 // yes    ldr x0,qAdrszMessSortOk    bl affichageMess100:                                               // 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 sZoneConvqAdrszCarriageReturn:     .quad szCarriageReturnqAdrsMessResult:          .quad sMessResultqAdrTableNumber:          .quad TableNumberqAdrszMessSortOk:         .quad szMessSortOkqAdrszMessSortNok:        .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 1b98:    mov x0,0                       // not sorted    b 100f99:    mov x0,1                       // sorted100:    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 i1:                             // start loop 1    ldr x4,[x0,x3,lsl 3]       // load value A[i]    sub x5,x3,1                // index j2:                             // 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 23:    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,01:                                   // 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,x2100:    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  ODRETURN 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:
```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;}`

`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

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   ODEND # 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 sorton 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 insertionSortproperty sort : insertionSort -- Demo:local aListset 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              *//*********************************/.dataszMessSortOk:       .asciz "Table sorted.\n"szMessSortNok:      .asciz "Table not sorted !!!!!.\n"sMessResult:        .ascii "Value  : "sMessValeur:        .fill 11, 1, ' '            @ size => 11szCarriageReturn:  .asciz "\n" .align 4iGraine:  .int 123456.equ NBELEMENTS,      10#TableNumber:      .int   1,3,6,2,5,9,10,8,4,7TableNumber:     .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 100f2:                                                 @ yes    ldr r0,iAdrszMessSortOk    bl affichageMess100:                                               @ 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 sMessValeuriAdrszCarriageReturn:    .int szCarriageReturniAdrsMessResult:          .int sMessResultiAdrTableNumber:          .int TableNumberiAdrszMessSortOk:         .int szMessSortOkiAdrszMessSortNok:        .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 1b100:    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 i1:                                                         @ start loop    ldr r4,[r0,r3,lsl #2]                                  @ load value A[i]    sub r5,r3,#1                                           @ index j2:    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 item3:    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,#01:                                                     @ 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 affichageMess100:    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,   10conversion10:    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,#02:    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,#' '                                       @ space3:    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`

## 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 runif [[ "\$0" == "bash" ]]; then # script is sourced     unset mainelse    main "[email protected]"                 # 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	NextEnd 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)	NextEnd 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 STRINGFOR L = 0 TO 10    n(L) = INT(RND * 32768)NEXTInsertionSort 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    NEXTEND SUB`
Output:
``` 1486 ; 9488 ; 9894 ; 17479 ; 18989 ; 23119 ; 23233 ; 24927 ; 25386 ; 26689 ;
```

### 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=911 REM GENERATE SOME RANDOM NUMBERS AND PRINT THEM12 FOR I=0 TO N: A(I)=INT(RND(1)*10)+1: NEXT: GOSUB 5020 FOR J=1 TO N:KEY=A(J): I=J-1: GOSUB 30: A(I+1)=KEY: NEXT: GOSUB 50: END30 IFI=-1 THEN RETURN31 IFA(I)>KEY THEN A(I+1)=A(I):I=I-1: GOTO 3032 RETURN50 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)+1200   NEXT210 END DEF220 DEF WRITE(REF A)230   FOR I=LBOUND(A) TO UBOUND(A)240     PRINT A(I);250   NEXT260   PRINT270 END DEF280 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-1330     LOOP340     LET A(I+1)=SW350   NEXT360 END DEF`

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

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

` (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    endend insertion_sort % Print an arrayprint_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.0identification 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)))))`

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

`subr sort  for i = 1 to len data[] - 1    h = data[i]    j = i - 1    while j >= 0 and h < data[j]      data[j + 1] = data[j]      j -= 1    .    data[j + 1] = h  ..data[] = [ 29 4 72 44 55 26 27 77 92 5 ]call sortprint 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        endcreate    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 5.0 :

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

## 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 FOREND 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  PRINTEND 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 send function include misc.econstant 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

`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    [email protected] 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 sorttest 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 doend 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 TimerFor i = a To b : array(i) = i  : NextFor 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 : PrintinsertionSort(array())  ' sort the arrayPrint "  sort ";For i = a To b : Print Using "####"; array(i); : Next : Print  ' empty keyboard bufferWhile Inkey <> "" : WendPrint : Print "hit any key to end program"SleepEnd`
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]```

`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) = valueENDDO`

## 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 Xlocal 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 Xend`

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 Mainbegin 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 simpnext  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 simpqed 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 sorteddef 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 Aend 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

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

## 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]}doneprintf "%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    printreturn`

## 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)	endend`
`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)  endendfunction isort(t)  local ret = {t[1], t[2]}  for i = 3, #t do    table.insert(ret, bins(ret, t[i]), t[i])  end  return retend 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:
```[email protected]{ 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 %forend %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) `

## 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 :: ysin foldl insert []end; insertion_sort Int.compare [6,8,5,9,3,2,1,4,7];`

## Modula-3

`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 \\\\[email protected].		\}.	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 \\\\[email protected].		\}.	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 Lend`

## 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 aecho a`
Output:
`@[-31, 0, 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    [] -> [x]  | y :: ys  when x <= y -> x :: y :: ys  | y :: ys -> y :: insert ys x ;;let insertion_sort = List.fold_left insert [];; insertion_sort [6;8;5;9;3;2;1;4;7];;`

## 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[email protected]J > Value do           A.(@J+1) := A[email protected]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};`

See Delphi

## 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 sortisort(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 listinsert([], 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  EndIfEndProcedure`

## 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 bisectdef 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  nextEnd Sub`

## REBOL

` ; This program works with REBOL version R2 and R3, to make it work with Red ; change the word func to functioninsertion-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]
```

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

## 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  endendary = [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  endend 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 = 0global inSortglobal 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 sortedfor i = 1 to sortEnd print i;" ";insSort(i)                  ' location and sorted datanext iwait function insertSort(x)                   ' Insert Sort Function i = 1while x > insSort(i) and i <= sortEnd  i = i + 1wendfor j = sortEnd to i step -1   insSort(j + 1) = insSort(j)next jinsSort(i) = xsortEnd    = sortEnd + 1end 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)

`DEFsort () = ()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 = 0readln	A<i = i + 1> = trim(input)	:s(readln)	aSize = i - 1 * sort array	i = 1loop1	value = A<i>	j = i - 1loop2	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 datawhile	output = A<i>; i = ?lt(i,aSize) i + 1	:s(while)end`

## Stata

`matavoid 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)&leq;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 [email protected] = 1 TO [email protected]    [email protected] = @([email protected])    [email protected] = [email protected]    DO WHILE ([email protected]>0) * ([email protected] < @(ABS([email protected])))        @([email protected]) = @([email protected])        [email protected] = [email protected] - 1    LOOP    @([email protected]) = [email protected]  NEXTRETURN  _Swap PARAM(2)                         ' Swap two array elements  PUSH @([email protected])  @([email protected]) = @([email protected])  @([email protected]) = 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 [email protected]    PRINT @(i),  NEXT   PRINTRETURN`

## 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 [email protected]`

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 1Private 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 = sEnd 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
`RandomizeDim 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 functionSub 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   NextEnd Sub `
Output:
```ORIGINAL : 26699;2643;10249;31612;21346;19702;29799;31115;20413;5197;
SORTED : 2643;5197;10249;19702;20413;21346;26699;29799;31115;31612;```

## 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 as = [ [4, 65, 2, -31, 0, 99, 2, 83, 782, 1], [7, 5, 2, 6, 1, 4, 2, 6, 3] ]for (a in as) {    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 as = [ [4, 65, 2, -31, 0, 99, 2, 83, 782, 1], [7, 5, 2, 6, 1, 4, 2, 6, 3] ]for (a in as) {    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 Lint  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 iend sub //--------------------------dim array(10)print "Antes de ordenar:"for i = 1 to 10    array(i) = int(ran(32768))    print array(i), " ";next iprintprint "\nDespues de ordenar:" InsertionSort(array()) for i = 1 to 10    print array(i), " ";next iprintend `

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