In [ ]:
%%HTML
<style>
.container { width:100% }
</style>
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 = L[:] # A is a copy of L
mergeSort(L, A)
The function mergeSort
is called with 2 arguments.
In [ ]:
def mergeSort(L, A):
n = 1
while n < len(L):
k = 0
while n * k + n < len(L):
top = min(n * k + 2 * n, len(L))
merge(L, n * k, n * k + n, top, A)
k += 2
n *= 2
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 [ ]:
import random as rnd
from collections import Counter
In [ ]:
def demo():
L = [ rnd.randrange(1, 100) for n in range(1, 20) ]
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 True
if 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 [ ]:
L = [ rnd.randrange(1000) for x in range(k) ]
In [ ]:
%%time
L = sort(L)
In [ ]:
help(sorted)
In [ ]:
6.5 / 0.309
In [ ]: