def sort(L):
    n = len(L)
    if n < 2:
        return L
    L1, L2 = L[:n//2], L[n//2:]
    return merge(sort(L1), sort(L2))

"""
Explanation: 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 two 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 \wedge \mathtt{n} := #L \rightarrow \mathtt{sort}(L) =
         \mathtt{merge}\bigl(\mathtt{sort}\bigl(\texttt{L[:n//2]}\bigr),
         \mathtt{sort}\bigl(\texttt{L[n//2:]}\bigr)\bigr)
   $$
   Here, $\texttt{L[:n//2]}$ is the first part of the list, while
   $\texttt{L[n//2:]}$ is the second part.  If the length of $L$ is even, both part have the same    number of elements, otherwise the second part has one element more than the first part.
End of explanation
"""


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 two sorted lists $L_1$ and $L_2$ are merged in a way that the resulting
list is also sorted.

If the list $L_1$ is empty, the result is $L_2$: 
   $$ \mathtt{merge}([], L_2) = L_2 $$
If the list $L_2$  is empty, the result is $L_1$: 
   $$ \mathtt{merge}(L_1, []) = L_1 $$
Otherwise, $L_1$ must have the form $[x_1] + R_1$ and $L_2$ has the form $[x_2] + R_2$.
   Then there is a case distinction with respect to the comparison of $x_1$ and $x_2$:
$x_1 \leq x_2$.
     In this case, we merge $R_1$ and $L_2$ and put $x_1$ at the beginning of this list:
     $$x_1 \leq x_2 \rightarrow \mathtt{merge}\bigl([x_1] + R_1, [x_2] + R_2\bigr) = 
     \bigl[x_1\bigr] + \mathtt{merge}\bigl(R_1,[x_2] + R_2\bigr)
     $$
$\neg (x_1 \leq x_2)$.
     In this case, we merge $L_1$ and $R_2$ and put $x_2$ at the beginning of this list:
     $$\neg (x_1 \preceq x_2) \rightarrow \mathtt{merge}\bigl([x_1] + R_1, [x_2] + R_2\bigr) 
       = \bigl[x_2 \bigr] + \mathtt{merge}\bigl([x_1] + R_1, R_2\bigr)
     $$
End of explanation
"""


import random as rnd

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


from collections import Counter

Counter(['a', 'b', 'a', 'b', 'c', 'a'])

def demo():
    L = [ rnd.randrange(1, 99+1) for n in range(1, 19+1) ]
    print("L = ", L)
    S = L[:]
    S = sort(S)
    print("S = ", S)
    print(Counter(L))
    print(Counter(S))
    print(Counter(L) == Counter(S))

demo()

"""
Explanation: We import the class Counter from the module collections.  This module provides us with a dictionary that keeps count
how many times an item occurs in a list.
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
"""


