isort Cons x xs r isort xs insert x r isort Nil r Nil insert S x r insert[Ite] < S x x S x r inssort xs isort xs Nil < S x S y < x y < 0 S y True < x 0 False insert[Ite] False x' Cons x xs Cons x insert x' xs insert[Ite] True x r Cons x r insert[Ite] 3 insert 2 True 0 S 1 < 2 Cons 2 Nil 0 0 0 isort 2 inssort 1 False 0 INNERMOST