def sort(L):
    n = len(L)
    if n < 2:
        return L
    L1, L2, L3 = L[:n//3], L[n//3:2*n//3], L[2*n//3:]
    return merge3(sort(L1), sort(L2), sort(L3))

"""
Explanation: Three-Way Merge Sort
In order to sort a list $L$ using <em style="color:blue;">merge sort</em> we proceed as follows:

If $L$ has less than two elements, then $L$ is already sorted.  Therefore we have: 
   $$ #L < 2 \rightarrow \mathtt{sort}(L) = L $$
Otherwise, the list $L$ is split into three lists that have approximately the same size.
   These lists are sorted recursively.  Then, the sorted lists are merged in a way that the
   resulting list is sorted: 
   $$ #L \geq 2 \rightarrow \mathtt{sort}(L) =
         \mathtt{merge3}\bigl(\mathtt{sort}\bigl(\texttt{L[:n//3]}\bigr),
                              \mathtt{sort}\bigl(\texttt{L[n//3:2$\cdot$n//3]}\bigr),
                              \mathtt{sort}\bigl(\texttt{L[2$\cdot$n//3:]}\bigr)\bigr)
   $$
   Here, L[:n//3] is the first part of the list, while
   L[n//3:2*n//3]} is the second part and L[2*n//3:] is the last part.
End of explanation
"""


def merge3(L1, L2, L3):
    if L1 == []:
        return merge(L2, L3)
    if L2 == []:
        return merge(L1, L3)
    if L3 == []:
        return merge(L1, L2)
    x1, *R1 = L1
    x2, *R2 = L2
    x3, *R3 = L3
    if x1 <= x2:
        if x1 <= x3:
            return [x1] + merge3(R1, L2, L3)
        else: # x3 < x1
            return [x3] + merge3(L1, L2, R3)
    else: # x2 < x1
        if x2 <= x3:
            return [x2] + merge3(L1, R2, L3)
        else: # x3 < x2
            return [x3] + merge3(L1, L2, R3)

def merge(L1, L2):
    if L1 == []:
        return L2
    if L2 == []:
        return L1
    x1, *R1 = L1
    x2, *R2 = L2
    if x1 <= x2:
        return [x1] + merge(R1, L2)
    else:
        return [x2] + merge(L1, R2)

sort([7, 8, 11, 12, 2, 5, 3, 7, 9, 3, 2])

"""
Explanation: We still need to specify how three sorted lists $L_1$, $L_2$, and $L_3$ are merged in a way that the 
resulting list is also sorted.

If the list $L_1$ is empty, the result is the merge of $L_2$ and $L_3$: 
   $$ \mathtt{merge3}([], L_2, L_3) = \mathtt{merge}(L_2, L_3) $$
If the list $L_2$ is empty, the result is the merge of $L_1$ and $L_3$: 
   $$ \mathtt{merge3}(L_2, [], L_3) = \mathtt{merge}(L_1, L_3) $$
If the list $L_3$ is empty, the result is the merge of $L_1$ and $L_2$: 
   $$ \mathtt{merge3}(L_1, L_2, []) = \mathtt{merge}(L_1, L_2) $$
Otherwise, the lists $L_1$, $L_2$, $L_3$ must have the form 
$L_1 = [x_1] + R_1$,
$L_2 = [x_2] + R_2$, and
$L_3 = [x_3] + R_3$.

Then there is a case distinction with respect to the minimum of $x_1$, $x_2$, and $x_3$:
   - $x_1 = \min(x_1, x_2, x_3) \rightarrow
     \mathtt{merge3}\bigl(L_1, L_2, L_3\bigr) = 
     \bigl[x_1\bigr] + \mathtt{merge}\bigl(R_1, L_2, L_3\bigr)$
   - $x_2 = \min(x_1, x_2, x_3) \rightarrow
     \mathtt{merge3}\bigl(L_1, L_2, L_3\bigr) = 
     \bigl[x_2\bigr] + \mathtt{merge}\bigl(L_1, R_2, L_3\bigr)$
   - $x_3 = \min(x_1, x_2, x_3) \rightarrow
     \mathtt{merge3}\bigl(L_1, L_2, L_3\bigr) = 
     \bigl[x_3\bigr] + \mathtt{merge}\bigl(L_1, L_2, R_3\bigr)$
End of explanation
"""


import random as rnd

from collections import Counter

"""
Explanation: Testing
We import the module random in order to be able to create lists of random numbers that are used for testing.
End of explanation
"""


def isOrdered(L):
    for i in range(len(L) - 1):
        assert L[i] <= L[i+1], f'{L} not ordered at {i}'

"""
Explanation: The function isOrdered(L) checks that the list L is sorted ascendingly.
End of explanation
"""


def sameElements(L, S):
    assert Counter(L) == Counter(S)

"""
Explanation: The function sameElements(L, S) returns Trueif the lists L and S contain the same elements and, furthermore, each 
element $x$ occurring in L occurs in S the same number of times it occurs in L.
End of explanation
"""


def testSort(n, k):
    for i in range(n):
        L = [ rnd.randrange(2*k) for x in range(k) ]
        S = sort(L)
        isOrdered(S)
        sameElements(L, S)
        print('.', end='')
    print()
    print("All tests successful!")

"""
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
"""


%%time
testSort(100, 2000)

"""
Explanation: Due to the recursion limit in Python we can only sort lists of length 2000.
End of explanation
"""


