data.list.sort

# Sorting algorithms on lists #

In this file we define list.sorted r l to be an alias for pairwise r l. This alias is preferred in the case that r is a < or ≤-like relation. Then we define two sorting algorithms: list.insertion_sort and list.merge_sort, and prove their correctness.

### The predicate list.sorted#

def list.sorted {α : Type u_1} (R : α → α → Prop) :
list α → Prop

sorted r l is the same as pairwise r l, preferred in the case that r is a < or ≤-like relation (transitive and antisymmetric or asymmetric)

Equations
Instances for list.sorted
@[protected, instance]
def list.decidable_sorted {α : Type uu} {r : α → α → Prop} (l : list α) :
Equations
@[simp]
theorem list.sorted_nil {α : Type uu} {r : α → α → Prop} :
theorem list.sorted.of_cons {α : Type uu} {r : α → α → Prop} {a : α} {l : list α} :
(a :: l) l
theorem list.sorted.tail {α : Type uu} {r : α → α → Prop} {l : list α} (h : l) :
l.tail
theorem list.rel_of_sorted_cons {α : Type uu} {r : α → α → Prop} {a : α} {l : list α} :
(a :: l)∀ (b : α), b lr a b
@[simp]
theorem list.sorted_cons {α : Type uu} {r : α → α → Prop} {a : α} {l : list α} :
(a :: l) (∀ (b : α), b lr a b) l
@[protected]
theorem list.sorted.nodup {α : Type uu} {r : α → α → Prop} [ r] {l : list α} (h : l) :
theorem list.eq_of_perm_of_sorted {α : Type uu} {r : α → α → Prop} [ r] {l₁ l₂ : list α} (p : l₁ ~ l₂) (s₁ : l₁) (s₂ : l₂) :
l₁ = l₂
theorem list.sublist_of_subperm_of_sorted {α : Type uu} {r : α → α → Prop} [ r] {l₁ l₂ : list α} (p : l₁ <+~ l₂) (s₁ : l₁) (s₂ : l₂) :
l₁ <+ l₂
@[simp]
theorem list.sorted_singleton {α : Type uu} {r : α → α → Prop} (a : α) :
[a]
theorem list.sorted.rel_nth_le_of_lt {α : Type uu} {r : α → α → Prop} {l : list α} (h : l) {a b : } (ha : a < l.length) (hb : b < l.length) (hab : a < b) :
r (l.nth_le a ha) (l.nth_le b hb)
theorem list.sorted.rel_nth_le_of_le {α : Type uu} {r : α → α → Prop} [ r] {l : list α} (h : l) {a b : } (ha : a < l.length) (hb : b < l.length) (hab : a b) :
r (l.nth_le a ha) (l.nth_le b hb)
theorem list.sorted.rel_of_mem_take_of_mem_drop {α : Type uu} {r : α → α → Prop} {l : list α} (h : l) {k : } {x y : α} (hx : x l) (hy : y l) :
r x y

### Insertion sort #

@[simp]
def list.ordered_insert {α : Type uu} (r : α → α → Prop) (a : α) :
list αlist α

ordered_insert a l inserts a into l at such that ordered_insert a l is sorted if l is.

Equations
@[simp]
def list.insertion_sort {α : Type uu} (r : α → α → Prop)  :
list αlist α

insertion_sort l returns l sorted using the insertion sort algorithm.

Equations
• (b :: l) = l)
@[simp]
theorem list.ordered_insert_nil {α : Type uu} (r : α → α → Prop) (a : α) :
= [a]
theorem list.ordered_insert_length {α : Type uu} (r : α → α → Prop) (L : list α) (a : α) :
L).length = L.length + 1
theorem list.ordered_insert_eq_take_drop {α : Type uu} (r : α → α → Prop) (a : α) (l : list α) :
l = list.take_while (λ (b : α), ¬r a b) l ++ a :: list.drop_while (λ (b : α), ¬r a b) l

An alternative definition of ordered_insert using take_while and drop_while.

theorem list.insertion_sort_cons_eq_take_drop {α : Type uu} (r : α → α → Prop) (a : α) (l : list α) :
(a :: l) = list.take_while (λ (b : α), ¬r a b) l) ++ a :: list.drop_while (λ (b : α), ¬r a b) l)
theorem list.perm_ordered_insert {α : Type uu} (r : α → α → Prop) (a : α) (l : list α) :
l ~ a :: l
theorem list.ordered_insert_count {α : Type uu} (r : α → α → Prop) [decidable_eq α] (L : list α) (a b : α) :
L) = L + ite (a = b) 1 0
theorem list.perm_insertion_sort {α : Type uu} (r : α → α → Prop) (l : list α) :
~ l
theorem list.sorted.insertion_sort_eq {α : Type uu} {r : α → α → Prop} {l : list α} (h : l) :
= l

If l is already list.sorted with respect to r, then insertion_sort does not change it.

theorem list.sorted.ordered_insert {α : Type uu} {r : α → α → Prop} [ r] [ r] (a : α) (l : list α) :
l l)
theorem list.sorted_insertion_sort {α : Type uu} (r : α → α → Prop) [ r] [ r] (l : list α) :
l)

The list list.insertion_sort r l is list.sorted with respect to r.

### Merge sort #

@[simp]
def list.split {α : Type uu} :
list αlist α × list α

Split l into two lists of approximately equal length.

split [1, 2, 3, 4, 5] = ([1, 3, 5], [2, 4])

Equations
theorem list.split_cons_of_eq {α : Type uu} (a : α) {l l₁ l₂ : list α} (h : l.split = (l₁, l₂)) :
(a :: l).split = (a :: l₂, l₁)
theorem list.length_split_le {α : Type uu} {l l₁ l₂ : list α} :
l.split = (l₁, l₂)l₁.length l.length l₂.length l.length
theorem list.length_split_lt {α : Type uu} {a b : α} {l l₁ l₂ : list α} (h : (a :: b :: l).split = (l₁, l₂)) :
l₁.length < (a :: b :: l).length l₂.length < (a :: b :: l).length
theorem list.perm_split {α : Type uu} {l l₁ l₂ : list α} :
l.split = (l₁, l₂)l ~ l₁ ++ l₂
def list.merge {α : Type uu} (r : α → α → Prop)  :
list αlist αlist α

Merge two sorted lists into one in linear time.

merge [1, 2, 4, 5] [0, 1, 3, 4] = [0, 1, 1, 2, 3, 4, 4, 5]

Equations
def list.merge_sort {α : Type uu} (r : α → α → Prop)  :
list αlist α

Implementation of a merge sort algorithm to sort a list.

Equations
theorem list.merge_sort_cons_cons {α : Type uu} (r : α → α → Prop) {a b : α} {l l₁ l₂ : list α} (h : (a :: b :: l).split = (l₁, l₂)) :
(a :: b :: l) = l₁) l₂)
theorem list.perm_merge {α : Type uu} (r : α → α → Prop) (l l' : list α) :
l l' ~ l ++ l'
theorem list.perm_merge_sort {α : Type uu} (r : α → α → Prop) (l : list α) :
~ l
@[simp]
theorem list.length_merge_sort {α : Type uu} (r : α → α → Prop) (l : list α) :
theorem list.sorted.merge {α : Type uu} {r : α → α → Prop} [ r] [ r] {l l' : list α} :
l l' l l')
theorem list.sorted_merge_sort {α : Type uu} (r : α → α → Prop) [ r] [ r] (l : list α) :
l)
theorem list.merge_sort_eq_self {α : Type uu} (r : α → α → Prop) [ r] [ r] [ r] {l : list α} :
l = l
theorem list.merge_sort_eq_insertion_sort {α : Type uu} (r : α → α → Prop) [ r] [ r] [ r] (l : list α) :
@[simp]
theorem list.merge_sort_nil {α : Type uu} (r : α → α → Prop)  :
@[simp]
theorem list.merge_sort_singleton {α : Type uu} (r : α → α → Prop) (a : α) :
[a] = [a]