\textbf{Algorithm}: Sorting Algorithm \#2
\textbf{Data}: a list L=(L[1], L[2], \ldots, L[n]) of integers
\textbf{Result}: L sorted in increasing order
\textbf{if} n=0,1 \textbf{then}
\quad \textbf{return} L
\textbf{end}
p \leftarrow \mathbf{D}(n) (L[p] is called a pivot in this case)
L_{1}, L_{2} \leftarrow \emptyset
\textbf{for} i=1,2, \ldots, p-1, p+1, \ldots, n \textbf{do}
\quad \textbf{if} L[i] \leq L[p] \textbf{then}
\quad \quad add L[i] to L_{1}
\quad \textbf{end}
\quad \textbf{else}
\quad \quad add L[i] to L_{2}
\quad \textbf{end}
\textbf{end}
use this algorithm to sort L_{1}, L_{2}
\textbf{return} \left[L_{1}, L[p], L_{2}\right]
Prove that this algorithm is correct and terminates.