void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i -1;
        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            j = j -1;
        }
        arr[j+1] = key;
    }
}

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i -1;
        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            j = j -1;
        }
        arr[j+1] = key;
    }
}

void insertionSort(int arr[]) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i -1;
        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            j = j -1;
        }
        arr[j+1] = key;
    }
}

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

function insertionSort(array $arr) {
    $n = count($arr);
    for ($i = 1; $i < $n; $i++) {
        $key = $arr[$i];
        $j = $i -1;
        while ($j >= 0 && $arr[$j] > $key) {
            $arr[$j+1] = $arr[$j];
            $j--;
        }
        $arr[$j+1] = $key;
    }
    return $arr;
}

sub insertionSort {
    my @arr = @_;
    my $n = scalar @arr;
    for (my $i = 1; $i < $n; $i++) {
        my $key = $arr[$i];
        my $j = $i -1;
        while ($j >= 0 && $arr[$j] > $key) {
            $arr[$j+1] = $arr[$j];
            $j--;
        }
        $arr[$j+1] = $key;
    }
    return @arr;
}

def insertionSort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i -1
        while j >= 0 and arr[j] > key:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key

def insertionSort(arr)
    (1...arr.length).each do |i|
        key = arr[i]
        j = i -1
        while j >= 0 && arr[j] > key
            arr[j+1] = arr[j]
            j -= 1
        end
        arr[j+1] = key
    end
    arr
end

procedure InsertionSort(var Arr: array of Integer);
var
    i, j, Key: Integer;
begin
    for i := 1 to High(Arr) do
    begin
        Key := Arr[i];
        j := i -1;
        while (j >= 0) and (Arr[j] > Key) do
        begin
            Arr[j + 1] := Arr[j];
            Dec(j);
        end;
        Arr[j + 1] := Key;
    end;
end;

fn insertionSort(arr: &mut[i32]) {
    for i in 1..arr.len() {
        let key = arr[i];
        let mut j = i;
        while j > 0 && arr[j-1] > key {
            arr[j] = arr[j-1];
            j -= 1;
        }
        arr[j] = key;
    }
}

mov ecx, 1
outer_loop:
    cmp ecx, n
    jge done
    mov eax, [arr + ecx*4]
    mov ebx, ecx
    inner_loop:
        test ebx, ebx
        jz insert
        mov edx, [arr + ebx*4 - 4]
        cmp edx, eax
        jle insert
        mov [arr + ebx*4], edx
        dec ebx
        jmp inner_loop
    insert:
        mov [arr + ebx*4], eax
        inc ecx
        jmp outer_loop
done:

function insertionSort(arr)
{
    for (var i = 1; i < arr.length; i++) {
        var key = arr[i];
        var j = i -1;
        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;
    }
}

function insertionSort(arr)
    for i = 2, #arr do
        local key = arr[i]
        local j = i -1
        while j >= 1 and arr[j] > key do
            arr[j+1] = arr[j]
            j = j -1
        end
        arr[j+1] = key
    end
end