-
Notifications
You must be signed in to change notification settings - Fork 109
feat: Mergesort Stability #438
Copy link
Copy link
Open
Description
I am working on a proof that the MergeSort implementation is stable, using the definition below. I am working off of the MergeSort implementation in #372. Would this be a welcome addition to the MergeSort file?
theorem mergeSort_stable
(xs : List α) (le : α → α → Bool)
[Std.Total (fun x y => le x y = true)]
[IsTrans _ (fun x y => le x y = true)] [DecidableEq α] :
let ys := (mergeSort xs).eval (sortModelNat le)
∀ k : α, ys.filter (fun x => le x k && le k x) = xs.filter (fun x => le x k && le k x) := by
sorryReactions are currently unavailable
Metadata
Metadata
Assignees
Labels
No labels