equal
deleted
inserted
replaced
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)" |