qs x' Cons x xs app Cons x Nil Cons x' quicksort xs quicksort Cons x Cons x' xs qs x part x Cons x' xs Nil Nil quicksort Cons x Nil Cons x Nil quicksort Nil Nil part x' Cons x xs xs1 xs2 part[Ite] > x' x x' Cons x xs xs1 xs2 part x Nil xs1 xs2 app xs1 xs2 app Cons x xs ys Cons x app xs ys app Nil ys ys notEmpty Cons x xs True notEmpty Nil False < S x S y < x y < 0 S y True < x 0 False > S x S y > x y > 0 y False > S x 0 True part[Ite] True x' Cons x xs xs1 xs2 part x' xs Cons x xs1 xs2 part[False][Ite] True x' Cons x xs xs1 xs2 part x' xs xs1 Cons x xs2 part[Ite] False x' Cons x xs xs1 xs2 part[False][Ite] < x' x x' Cons x xs xs1 xs2 part[False][Ite] False x' Cons x xs xs1 xs2 part x' xs xs1 xs2 part 4 True 0 app 2 Nil 0 part[False][Ite] 5 quicksort 1 part[Ite] 5 qs 2 > 2 < 2 S 1 Cons 2 0 0 notEmpty 1 False 0 INNERMOST Frederiksen_Others/quicksortPtime.tml.trs