no goals
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
⊢ Sorted r (mergeSort r [])
simp [mergeSort]
no goals
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a : α
⊢ Sorted r (mergeSort r [a])
simp [mergeSort]
case mk
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a b : α
l l₁ l₂ : List α
e : split (a :: b :: l) = (l₁, l₂)
⊢ Sorted r (mergeSort r (a :: b :: l))
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a b : α
l : List α
⊢ Sorted r (mergeSort r (a :: b :: l))
cases' e : split (a :: b :: l) with l₁ l₂
case mk.intro
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a b : α
l l₁ l₂ : List α
e : split (a :: b :: l) = (l₁, l₂)
h₁ : length l₁ < length (a :: b :: l)
h₂ : length l₂ < length (a :: b :: l)
⊢ Sorted r (mergeSort r (a :: b :: l))
case mk
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a b : α
l l₁ l₂ : List α
e : split (a :: b :: l) = (l₁, l₂)
⊢ Sorted r (mergeSort r (a :: b :: l))
cases' length_split_lt e with h₁ h₂
case mk.intro
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a b : α
l l₁ l₂ : List α
e : split (a :: b :: l) = (l₁, l₂)
h₁ : length l₁ < length (a :: b :: l)
h₂ : length l₂ < length (a :: b :: l)
⊢ Sorted r (merge r (mergeSort r l₁) (mergeSort r l₂))
case mk.intro
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a b : α
l l₁ l₂ : List α
e : split (a :: b :: l) = (l₁, l₂)
h₁ : length l₁ < length (a :: b :: l)
h₂ : length l₂ < length (a :: b :: l)
⊢ Sorted r (mergeSort r (a :: b :: l))
rw [mergeSort_cons_cons r e]
no goals
case mk.intro
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a b : α
l l₁ l₂ : List α
e : split (a :: b :: l) = (l₁, l₂)
h₁ : length l₁ < length (a :: b :: l)
h₂ : length l₂ < length (a :: b :: l)
⊢ Sorted r (merge r (mergeSort r l₁) (mergeSort r l₂))
exact (sorted_mergeSort l₁).merge (sorted_mergeSort l₂)