AFTD Auto-Formalizing Theoretical Domains

Cslib.Algorithms.Lean.TimeM.mergeSort

defimported Lean

Sorts a list using the merge sort algorithm, counting comparisons as time cost. Returns a TimeM ℕ (List α) where the time represents the total number of comparisons.

Statement

set_option relaxedAutoImplicit true in
open Cslib Cslib.Algorithms Cslib.Algorithms.Lean Cslib.Algorithms.Lean.TimeM in
set_option autoImplicit false in
variable {α : Type} [LinearOrder α] in
def Cslib.Algorithms.Lean.TimeM.mergeSort (xs : List α) : TimeM ℕ (List α)
Defined in
CSLib, `Cslib.Algorithms.Lean.TimeM.mergeSort`
Lean proof
By Sorrachai Yingchareonthawornhcai, from github.com/leanprover/cslib at 3951377e5a3f (Copyright (c) 2025 Sorrachai Yingchareonthawornhcai. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.33.0.
Verified
08 Oct 2026
Axioms
none listed
Built on 24
Used by 6

Lean source view module on GitHub

set_option relaxedAutoImplicit true in
open Cslib Cslib.Algorithms Cslib.Algorithms.Lean Cslib.Algorithms.Lean.TimeM in
set_option autoImplicit false in
variable {α : Type} [LinearOrder α] in
/-- Sorts a list using the merge sort algorithm, counting comparisons as time cost. Returns a `TimeM ℕ (List α)` where the time represents the total number of comparisons. -/
def Cslib.Algorithms.Lean.TimeM.mergeSort (xs : List α) : TimeM ℕ (List α) :=  do
  if xs.length < 2 then return xs
  else
    let half  := xs.length / 2
    let left  := xs.take half
    let right := xs.drop half
    let sortedLeft  ← mergeSort left
    let sortedRight ← mergeSort right
    merge sortedLeft sortedRight
See it in the graphDiscuss this resultChallenge it