<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Merge Sort
In order to sort a list $L$ using <em style="color
Step1:  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$
Step2:  Testing
We import the module random in order to be able to create lists of random numbers that are used for testing.
Step3:  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.
Step4:  The function isOrdered(L) checks that the list L is sorted ascendingly.
Step5:  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.
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:  Due to the recursion limit in Python we can only sort lists of length 2000.
<ASSISTANT_TASK:>
Python Code:
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
<END_TASK>