%if False

This is an example file that demonstrates the use of lhs2TeX.
Compile it with

lhs2TeX --math Sort.lhs > Sort.tex

and then run it through LaTeX.

The "if False" in the first line is an lhs2TeX directive. All
directives start with a % character. You can use the "if" directive to
conditionally include or exclude certain parts of your document. An
"if False" statement can be used to start a comment that will not
appear in the TeX output.

To make this a valid TeX document, we will start with a \documentclass
command, after closing this comment block by means of an "endif"
directive.

%endif

\documentclass{article}

%if False
We will now include the two files that are required for
using lhs2TeX, using the "include" directive.
To activate alignment of the code blocks, we set the
alignment column to 33, using the "align" directive.
%endif

%include lhs2TeX.fmt
%include lhs2TeX.sty
%align 33

%if False

Another use for conditionals is to exclude parts of the code
that are needed to make the module correct Haskell, but should
not appear in the typeset version. We place the Haskell module
header here.

> module Sort where

Now we start the TeX document with \begin{document}
and then include the module body that will be typeset:

%endif

\begin{document}

> quickSort                     :: (Ord a) => [a] -> [a]
> quickSort []                  =  []
> quickSort (a : as)            =  quickSort [ b | b <- as, b <= a ]
>                               ++ a : quickSort [ b | b <- as, b > a ]
>
> mergeSort                     :: (Ord a) => [a] -> [a]
> mergeSort []                  =  []
> mergeSort [a]                 =  [a]
> mergeSort as                  =  merge (mergeSort bs) (mergeSort cs)
>     where (bs, cs)            =  splitAt (length as `div` 2) as

The worst case execution time of |mergeSort| is $\Theta(n\log n)$.
NB. |splitAt| is given by

< splitAt                       :: Int -> [a] -> ([a], [a])
< splitAt k as                  =  (take k as, drop k as) {-"\enskip."-}

%if False
Finally, we have to end the LaTeX document and are done.
%endif

\end{document}