Merges two sorted slices of one contiguous memory

mergeInPlace.zig

const std = @import("std");

fn mergeInPlace(comptime T: type, s: []T, midpoint: usize) void {
    std.debug.assert(midpoint <= s.len);
    if (midpoint == 0 or midpoint == s.len) return;

    var a: usize = 0;
    var b: usize = midpoint;
    var c: usize = midpoint;

    var i: usize = 0;

    // Objective: Make `a` and `c` meet
    while (true) {
        // Shrink slice `a..b` by shifting `a`
        while (s[a] <= s[c]) : (a += 1) {
            if (a == c) return;
        }
        b = @max(a+1, b);

        // Insert min(s[b],s[c]) in s[a] and rotate insert the previous s[a] into `b..c` slice
        const prev_a = s[a];

        if (s[b] < s[c]) {
            s[a] = s[b];

            // Rotate left
            i = b;
            while (i < c-1 and prev_a >= s[i]) : (i += 1) {}

            var j: usize = b;
            while (j < i) : (j += 1) {
                s[j] = s[j+1];
            }
        } else {
            s[a] = s[c];

            // Rotate right
            i = b;
            while (i < c and prev_a >= s[i]) : (i += 1) {}

            var j: usize = c;
            while (j > i) : (j -= 1) {
                s[j] = s[j-1];
            }
        }

        s[i] = prev_a;

        a += 1;
        b = @max(a+1, b);
        c = @min(c+1, s.len-1);

        // Shrink slice `b..c` by shifting `c`
        while (b < c and s[c-1] <= s[c]) : (c -= 1) {
            if (a == c) return;
        }
    }
}

test {
    const arr_len = 20;
    const rand_seed = 532;
    const sorted = comptime blk: {
        var a = [_]u8{0} ** arr_len;
        var i = 0;
        while (i < arr_len) : (i += 1) {
            a[i] = i + 1;
        }
        break :blk a;
    };

    var default_prng = std.rand.DefaultPrng.init(rand_seed);
    var rng = default_prng.random();
    var arr = [_]u8{0} ** arr_len;
    var i: u16 = 0;
    while (i < 10000) : (i += 1) {
        const midpoint = rng.uintLessThan(u8, arr_len);
        var a: u8 = 0;
        var b: u8 = midpoint;
        for (sorted) |n| {
            if (a == midpoint) {
                arr[b] = n;
                b += 1;
                continue;
            }
            if (b == arr_len) {
                arr[a] = n;
                a += 1;
                continue;
            }

            if (rng.boolean()) {
                arr[a] = n;
                a += 1;
            } else {
                arr[b] = n;
                b += 1;
            }
        }

        std.debug.print("\nBefore: {any}\n", .{arr});
        mergeInplace(u8, &arr, midpoint);
        std.debug.print("After: {any}\n", .{arr});
        try std.testing.expectEqual(sorted, arr);
    }
}