<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 An Array-Based Implementation of Dual-Pivot-Quicksort
Step1:  The function $\texttt{sort}(L)$ sorts the list $L$ in place.
Step2:  The function $\texttt{quickSort}(a, b, L)$ sorts the sublist $L[a
Step3:  The function $\texttt{partition}(\texttt{start}, \texttt{end}, L)$ returns two indices $m_1$ and $m_2$ 
into the list $L$ and regroups the elements of $L$ such that after the function returns the following holds
Step4:  The function $\texttt{swap}(x, y, L)$ swaps the elements at index $x$ and $y$ in $L$.
Step5:  Testing
Step6:  The function $\texttt{testSort}(n, k)$ generates $n$ random lists of length $k$, sorts them, and checks whether the output is sorted and contains the same elements as the input.
Step7:  Next, we sort a million random integers.
Step8:  Again, we sort a million integers.  This time, many of the integers have the same value.
<ASSISTANT_TASK:>
Python Code:
import random as rnd
Explanation: An Array-Based Implementation of Dual-Pivot-Quicksort
End of explanation
def sort(L):
    quickSort(0, len(L) - 1, L)
Explanation: The function $\texttt{sort}(L)$ sorts the list $L$ in place.
End of explanation
def quickSort(a, b, L):
    if b <= a:
        return  # at most one element, nothing to do
    x1, x2 = L[a], L[b]
    if x1 > x2:
        swap(a, b, L)
    m1, m2 = partition(a, b, L)  # m1 and m2 are the split indices
    quickSort(a, m1 - 1, L)
    if L[m1] != L[m2]:
        quickSort(m1 + 1, m2 - 1, L)
    quickSort(m2 + 1, b, L)
Explanation: The function $\texttt{quickSort}(a, b, L)$ sorts the sublist $L[a:b+1]$ in place.
End of explanation
def partition(start, end, L):
    p1 = L[start]
    p2 = L[end]
    idxLeft   = start
    idxMiddle = start + 1
    idxRight  = end
    while idxMiddle < idxRight:
        x = L[idxMiddle]
        if x < p1:
            idxLeft += 1
            swap(idxLeft, idxMiddle, L)
            idxMiddle += 1
        elif x <= p2:
            idxMiddle += 1
        else: 
            idxRight -= 1
            swap(idxMiddle, idxRight, L)
    swap(start, idxLeft, L)
    swap(end, idxRight, L)
    return idxLeft, idxRight
Explanation: The function $\texttt{partition}(\texttt{start}, \texttt{end}, L)$ returns two indices $m_1$ and $m_2$ 
into the list $L$ and regroups the elements of $L$ such that after the function returns the following holds:
$\forall i \in {\texttt{start}, \cdots, m_1-1} : L[i]    <   L[m_1]$,
$\forall i \in { m_1+1, \cdots, m_2-1 }        : L[m_1] \leq L[i] \leq L[m_2]$,
$\forall i \in { m_2+1, \cdots, \texttt{end} } : L[m_2]  <   L[i]$,
$L[m_1] = p_1$,
$L[m_2] = p_2$.
Here, $p_1$ is the element that is at the index $\texttt{start}$ at the time of the invocation 
of the function, while $p_2$ is the elements at index $\texttt{end}$.  It is assumed that $p_1 \leq p_2$.
The for-loop of partition maintains the following invariants:
$L[\texttt{start}] = p_1$,
$L[\texttt{end}]   = p_2$,
$\forall i \in {\texttt{start} + 1, \cdots, \texttt{idxLeft} } : L[i] < p_1$
$\forall i \in {\texttt{idxLeft} + 1, \cdots, \texttt{idxMiddle} - 1} : p_1 \leq L[i] \leq p_2$
$\forall i \in {\texttt{idxRight}, \cdots, \texttt{end}-1} : p_2 < L[i]$
End of explanation
def swap(x, y, L):
    L[x], L[y] = L[y], L[x]
Explanation: The function $\texttt{swap}(x, y, L)$ swaps the elements at index $x$ and $y$ in $L$.
End of explanation
L = [5, 7, 9, 1, 24, 11, 5, 2, 5, 8, 2, 13, 9]
print(L)
p1, p2 = partition(0, len(L) - 1, L)
print(L[:p1], L[p1], L[p1+1:p2], L[p2], L[p2+1:])
def demo():
    L = [ rnd.randrange(1, 200) for n in range(1, 16) ]
    print("L = ", L)
    sort(L)
    print("L = ", L)
demo()
def isOrdered(L):
    for i in range(len(L) - 1):
        assert L[i] <= L[i+1]
from collections import Counter
def sameElements(L, S):
    assert Counter(L) == Counter(S)
Explanation: Testing
End of explanation
def testSort(n, k):
    for i in range(n):
        L = [ rnd.randrange(2*k) for x in range(k) ]
        oldL = L[:]
        sort(L)
        isOrdered(L)
        sameElements(oldL, L)
        assert len(L) == len(oldL)
        print('.', end='')
    print()
    print("All tests successful!")
%%time
testSort(100, 20_000)
Explanation: The function $\texttt{testSort}(n, k)$ generates $n$ random lists of length $k$, sorts them, and checks whether the output is sorted and contains the same elements as the input.
End of explanation
%%timeit
k = 1_000_000
L = [ rnd.randrange(2 * k) for x in range(k) ]
sort(L)
Explanation: Next, we sort a million random integers.
End of explanation
%%timeit
k = 1_000_000
L = [ rnd.randrange(1000) for x in range(k) ]
sort(L)
Explanation: Again, we sort a million integers.  This time, many of the integers have the same value.
End of explanation
<END_TASK>