tender lily
Almost have a full merge sort algo without any stack allocations.
The issue that I'm running into is that I need to get the correct length of the arrays before copying into them
It could also be that it's impossible using memcpy
const std = @import("std");
const testing = std.testing;
const print = std.debug.print;
fn merge(array: []u8, left: u32, mid: u32, right: u32) void {
const n1 = mid - left + 1;
const n2 = right - mid;
var left_arr = [_]u8{0} ** 4;
var right_arr = [_]u8{0} ** 4;
@memcpy(left_arr[0..n1], array[left .. mid + 1]);
@memcpy(right_arr[0..n1], array[mid + 1 .. right + 1]);
var i: u32 = 0;
var j: u32 = 0;
var k: u32 = left;
while (i < n1 and j < n2) {
if (left_arr[i] <= right_arr[j]) {
array[k] = left_arr[i];
i += 1;
} else {
array[k] = right_arr[j];
j += 1;
}
k += 1;
}
// Copy the remaining elements of left_arr, if any
while (i < n1) {
array[k] = left_arr[i];
i += 1;
k += 1;
}
// Copy the remaining elements of right_arr, if any
while (j < n2) {
array[k] = right_arr[j];
j += 1;
k += 1;
}
}
fn merge_sort(array: []u8, left: u32, right: u32) void {
if (left < right) {
const l: f32 = @floatFromInt(left);
const r: f32 = @floatFromInt(right);
const midpoint: u32 = @intFromFloat(@floor(l + (r - l) / 2));
merge_sort(array, left, midpoint);
merge_sort(array, midpoint + 1, right);
merge(array, left, midpoint, right);
}
}
test "merge sort" {
var array = [_]u8{ 38, 27, 43, 10, 1, 5 };
merge_sort(&array, 0, array.len - 1);
print("{any}\n", .{array});
}
delicate quarry
old jetty