merge sort

2 files changed, 80 insertions, 3 deletions

diff --git a/src/benchmark.zig b/src/benchmark.zig
index c44fb11..6781b5a 100644
--- a/src/benchmark.zig
+++ b/src/benchmark.zig
@@ -5,15 +5,18 @@ const bubble = @import("sort/bubble.zig");
 const selection = @import("sort/selection.zig");
 const insertion = @import("sort/insertion.zig");
 const shell = @import("sort/shell.zig");
+const merge = @import("sort/merge.zig");
 const testing = std.testing;
+const Allocator = std.mem.Allocator;
 
 fn benchmark(comptime T: type, comptime sort_fn: fn (type, []T) void, n: usize, runs: usize) !u64 {
-    var prng = std.rand.DefaultPrng.init(0);
+    var prng = Random.DefaultPrng.init(0);
     var random = prng.random();
+    var allocator = testing.allocator;
     var total_time: u64 = 0;
     for (0..runs) |_| {
-        const list = try testing.allocator.alloc(T, n);
-        defer testing.allocator.free(list);
+        const list = try allocator.alloc(T, n);
+        defer allocator.free(list);
         for (list) |*item| {
             item.* = random.int(T);
         }
@@ -25,6 +28,25 @@ fn benchmark(comptime T: type, comptime sort_fn: fn (type, []T) void, n: usize,
     return total_time / runs;
 }
 
+fn benchmark_merge(comptime T: type, n: usize, runs: usize) !u64 {
+    var prng = Random.DefaultPrng.init(0);
+    var random = prng.random();
+    var total_time: u64 = 0;
+    var allocator = testing.allocator;
+    for (0..runs) |_| {
+        const list = try allocator.alloc(T, n);
+        defer allocator.free(list);
+        for (list) |*item| {
+            item.* = random.int(T);
+        }
+        const start = time.milliTimestamp();
+        try merge.sort(T, list, &allocator);
+        const end = time.milliTimestamp();
+        total_time += @intCast(end - start);
+    }
+    return total_time / runs;
+}
+
 fn run_bench(comptime T: type, comptime sort_fn: fn (type, []T) void, name: []const u8) !void {
     const runs = 10;
     const sizes = [_]usize{ 100, 1000, 10000 };
@@ -35,9 +57,20 @@ fn run_bench(comptime T: type, comptime sort_fn: fn (type, []T) void, name: []co
     }
 }
 
+fn run_bench_merge(comptime T: type, name: []const u8) !void {
+    const runs = 10;
+    const sizes = [_]usize{ 100, 1000, 10000 };
+    std.debug.print("\n{s} Benchmark:\n", .{name});
+    for (sizes) |size| {
+        const avg_time = try benchmark_merge(T, size, runs);
+        std.debug.print("Average time for N={d}: {d} ms\n", .{ size, avg_time });
+    }
+}
+
 test "sorting benchmarks" {
     try run_bench(i64, bubble.sort, "Bubble Sort");
     try run_bench(i64, selection.sort, "Selection Sort");
     try run_bench(i64, insertion.sort, "Insertion Sort");
     try run_bench(i64, shell.sort, "Shell Sort");
+    try run_bench_merge(i64, "Merge Sort");
 }
diff --git a/src/sort/merge.zig b/src/sort/merge.zig
new file mode 100644
index 0000000..e93b2bd
--- /dev/null
+++ b/src/sort/merge.zig
@@ -0,0 +1,44 @@
+const std = @import("std");
+const mem = std.mem;
+const testing = std.testing;
+const Allocator = std.mem.Allocator;
+
+fn sort_helper(comptime T: type, arr: []T, aux: []T, low: usize, high: usize) void {
+    if (high - low <= 1) return;
+    const mid = low + (high - low) / 2;
+    sort_helper(T, arr, aux, low, mid);
+    sort_helper(T, arr, aux, mid, high);
+    merge(T, arr, aux, low, mid, high);
+}
+
+fn merge(comptime T: type, arr: []T, aux: []T, low: usize, mid: usize, high: usize) void {
+    @memcpy(aux[low..high], arr[low..high]);
+    var i = low;
+    var j = mid;
+    var k = low;
+    while (k < high) : (k += 1) {
+        if (i < mid and (j == high or aux[i] <= aux[j])) {
+            arr[k] = aux[i];
+            i += 1;
+        } else {
+            arr[k] = aux[j];
+            j += 1;
+        }
+    }
+}
+
+pub fn sort(comptime T: type, arr: []T, allocator: *Allocator) !void {
+    const aux = try allocator.alloc(T, arr.len);
+    defer allocator.free(aux);
+    sort_helper(T, arr, aux, 0, arr.len);
+    std.debug.print("aux: {any}\n", .{aux});
+    std.debug.print("arr: {any}\n", .{arr});
+}
+
+test "optimized merge sort - basic test" {
+    var arr = [_]i64{ 20, 3, 5, 1, 30, 4, 2 };
+    var allocator = testing.allocator;
+    try sort(i64, &arr, &allocator);
+    const expected = [_]i64{ 1, 2, 3, 4, 5, 20, 30 };
+    try testing.expectEqualSlices(i64, &expected, &arr);
+}