def sort(L):
    A = L[:]
    mergeSort(L, 0, len(L), A)

"""
Explanation: Merge Sort: A Recursive, Array Based Implementation
The function $\texttt{sort}(L)$ sorts the list $L$ in place using <em style="color:blue">merge sort</em>.
It takes advantage of the fact that, in Python, lists are stored internally as arrays.
The function sort is a wrapper for the function merge_sort.  Its sole purpose is to allocate the auxiliary array A, 
which has the same size as the array holding L.
End of explanation
"""


def mergeSort(L, start, end, A):
    if end - start < 2:
        return
    middle = (start + end) // 2
    mergeSort(L, start,  middle, A)
    mergeSort(L, middle, end   , A)
    merge(L, start, middle, end, A)

"""
Explanation: The function mergeSort is called with 4 arguments.
  - The first parameter $\texttt{L}$ is the list that is to be sorted.
    However, the task of $\texttt{mergeSort}$ is not to sort the entire list $\texttt{L}$ but only
    the part of $\texttt{L}$ that is given as
    $$\texttt{L[start:end]}$$ 
  - Hence, the parameters $\texttt{start}$ and $\texttt{end}$ are indices specifying the 
    subarray that needs to be sorted.
  - The final parameter $\texttt{A}$ is used as an auxiliary array.  This array is needed
    as <em style="color:blue">temporary storage</em> and is required to have the same size as the list $\texttt{L}$.
End of explanation
"""


def merge(L, start, middle, end, A):
    A[start:end] = L[start:end]
    idx1 = start
    idx2 = middle
    i    = start
    while idx1 < middle and idx2 < end:
        if A[idx1] <= A[idx2]:
            L[i]  = A[idx1]
            idx1 += 1
        else:
            L[i]  = A[idx2]
            idx2 += 1
        i += 1
    if idx1 < middle:
        L[i:end] = A[idx1:middle]
    if idx2 < end:
        L[i:end] = A[idx2:end]

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

"""
Explanation: The function merge takes five arguments.
  - L      is a list,
  - start  is an integer such that $\texttt{start}  \in {0, \cdots, \texttt{len}(L)-1 }$,
  - middle is an integer such that $\texttt{middle} \in {0, \cdots, \texttt{len}(L)-1 }$,
  - end    is an integer such that $\texttt{end}    \in {0, \cdots, \texttt{len}(L)-1 }$, 
  - A      is a list of the same length as L.
Furthermore, the indices start, middle, and end have to satisfy the following:
$$ 0 \leq \texttt{start} < \texttt{middle} < \texttt{end} \leq \texttt{len}(L) $$
The function assumes that the sublists L[start:middle] and L[middle:end] are already sorted.
The function merges these sublists so that when the call returns the sublist L[start:end]
is sorted.  The last argument A is used as auxiliary memory.
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 then sorted.
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[:]
    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 sorted at index {i}'

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


def sameElements(L, S):
    assert Counter(L) == Counter(S), f'{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) ]
        oldL = L[:]
        sort(L)
        isOrdered(L)
        sameElements(oldL, L)
        print('.', end='')
    print()
    print("All tests successful!")

%%time
testSort(100, 20000)

%%time
k = 1_000_000
L = [ rnd.randrange(2*k) for x in range(k) ]
sort(L)

"""
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) ]
S = sorted(L)

"""
Explanation: The predefined function sorted is a lot quicker:
End of explanation
"""


