Skip to content

feat: Mergesort Stability #438

@Arleee1

Description

@Arleee1

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
  sorry

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions