src/HOL/Data_Structures/Sorting.thy
changeset 69597 ff784d5a5bfb
parent 69036 3ab140184a14
child 70250 20d819b0a29d
equal deleted inserted replaced
69596:c8a2755bf220 69597:ff784d5a5bfb
   372 done
   372 done
   373 
   373 
   374 
   374 
   375 subsection "Insertion Sort w.r.t. Keys and Stability"
   375 subsection "Insertion Sort w.r.t. Keys and Stability"
   376 
   376 
   377 text \<open>Note that @{const insort_key} is already defined in theory @{theory HOL.List}.
   377 text \<open>Note that \<^const>\<open>insort_key\<close> is already defined in theory \<^theory>\<open>HOL.List\<close>.
   378 Thus some of the lemmas are already present as well.\<close>
   378 Thus some of the lemmas are already present as well.\<close>
   379 
   379 
   380 fun isort_key :: "('a \<Rightarrow> 'k::linorder) \<Rightarrow> 'a list \<Rightarrow> 'a list" where
   380 fun isort_key :: "('a \<Rightarrow> 'k::linorder) \<Rightarrow> 'a list \<Rightarrow> 'a list" where
   381 "isort_key f [] = []" |
   381 "isort_key f [] = []" |
   382 "isort_key f (x # xs) = insort_key f x (isort_key f xs)"
   382 "isort_key f (x # xs) = insort_key f x (isort_key f xs)"