

In [ ]:

    
%%HTML
<style>
.container { width:100% } 
</style>

Merge Sort: A Recursive, Array Based Implementation

The function $\texttt{sort}(L)$ sorts the list $L$ in place using merge sort. 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.



In [ ]:

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

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 temporary storage and is required to have the same size as the list $\texttt{L}$.



In [ ]:

    
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)

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.



In [ ]:

    
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]



In [ ]:

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

Testing

We import the module random in order to be able to create lists of random numbers that are then sorted.



In [ ]:

    
import random as rnd

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.



In [ ]:

    
from collections import Counter



In [ ]:

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



In [ ]:

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



In [ ]:

    
demo()

The function isOrdered(L) checks that the list L is sorted in ascending order.



In [ ]:

    
def isOrdered(L):
    for i in range(len(L) - 1):
        assert L[i] <= L[i+1]

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.



In [ ]:

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

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.



In [ ]:

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



In [ ]:

    
%%time
testSort(100, 20000)



In [ ]:

    
k = 1000000
L = [ rnd.randrange(2*k) for x in range(k) ]



In [ ]:

    
%%time
sort(L)



In [ ]: