From 66665caf9da212c121c99de95a18e6ae3470cdbc Mon Sep 17 00:00:00 2001
From: Vladimir Azarov <avm@intermediate-node.net>
Date: Sun, 10 Aug 2025 22:01:56 +0200
Subject: String literal deduplication

---
 common.sml | 26 ++++++++++++++++++++++++++
 1 file changed, 26 insertions(+)

(limited to 'common.sml')

diff --git a/common.sml b/common.sml
index 7ed59c3..5f4eaae 100644
--- a/common.sml
+++ b/common.sml
@@ -4,6 +4,32 @@ fun $ (x, y) = x y
 infixr 0 $
 fun id x = x
 
+val compare = fn a => fn b => Int.compare (a, b)
+
+fun sort _ [] = []
+  | sort _ [x] = [x]
+  | sort le l =
+  let
+    fun divide [] accp = accp
+      | divide [x] (acc1, acc2) = (x :: acc1, acc2)
+      | divide (x :: y :: tail) (acc1, acc2) =
+        divide tail (x :: acc1, y :: acc2)
+    val (part1, part2) = divide l ([], [])
+    val part1 = sort le part1
+    val part2 = sort le part2
+
+    fun merge [] [] acc = acc
+      | merge [] ys acc = rev $ List.revAppend (ys, acc)
+      | merge xs [] acc = rev $ List.revAppend (xs, acc)
+      | merge (x :: xs) (y :: ys) acc =
+          if le (x, y) then
+            merge xs (y :: ys) (x :: acc)
+          else
+            merge (x :: xs) ys (y :: acc)
+  in
+    merge part1 part2 []
+  end
+
 fun assert truth = if not truth then raise Unreachable else ()
 
 structure Fold = struct
-- 
cgit v1.2.3