Algorithms: Sorting

function insertion_sort(array &$a): int {
    alg_require(array_is_list($a));
    $n = count($a);
    alg_require((($n >= 0) && ($n <= 1000000)));
    alg_require((count($a) == $n));
    $i = 1;
    $j = 0;
    $key = 0;
    while (($i < $n)) {
        $key = $a[$i];
        $j = alg_sub($i, 1);
        while ((($j >= 0) && ($a[$j] > $key))) {

function merge_sort(array &$a): int {
    alg_require(array_is_list($a));
    $n = count($a);
    alg_require((($n >= 0) && ($n <= 1000000)));
    alg_require((count($a) == $n));
    $buf = array_fill(0, alg_size(alg_add($n, 1)), 0);
    $width = 1;
    $left = 0;
    $mid = 0;
    $right = 0;
    $i = 0;
    $j = 0;

    static int shell_sort(int[] a) {
        java.util.Objects.requireNonNull(a, "a");
        int n = a.length;
        alg_require(((n >= 0) && (n <= 1000000)));
        alg_require((a.length == n));
        int gap = (n / 2);
        int i = 0;
        int j = 0;
        int key = 0;
        while ((gap > 0)) {
            i = gap;
            while ((i < n)) {

    static int selection_sort(int[] a) {
        java.util.Objects.requireNonNull(a, "a");
        int n = a.length;
        alg_require(((n >= 0) && (n <= 1000000)));
        alg_require((a.length == n));
        int i = 0;
        int j = 0;
        int best = 0;
        int temp = 0;
        while ((i < n)) {
            best = i;
            j = Math.addExact(i, 1);

    static int bubble_sort(int[] a) {
        java.util.Objects.requireNonNull(a, "a");
        int n = a.length;
        alg_require(((n >= 0) && (n <= 1000000)));
        alg_require((a.length == n));
        int end = Math.subtractExact(n, 1);
        int i = 0;
        int swapped = 0;
        int temp = 0;
        while ((end > 0)) {
            swapped = 0;
            i = 0;