In [20]:
from heapq import heappush, heappop, merge
# documentation: https://docs.python.org/3.4/library/heapq.html
from math import ceil
## the heap is essentially a min-heap
DEBUG = True
def p(msg):
if DEBUG:
print('.. {}'.format(msg))
## making use of the heapq.merge() function to simulate the in-memory heap based merging
## (see source at https://fossies.org/dox/Python-3.5.2/heapq_8py_source.html)
def merge_runs(list_of_runs):
return list(merge(*list_of_runs))
In [29]:
import random
random.seed(1999)
n1 = n2 = 5
n3 = 2
run1 = sorted([random.randint(1, 100) for _ in range(n1)])
run2 = sorted([random.randint(1, 100) for _ in range(n2)])
run3 = sorted([random.randint(1, 100) for _ in range(n3)])
print(run1, run2, run3)
runs = [run1, run2, run3]
new_run = merge_runs(runs)
print(new_run)
In [ ]:
def multiway_merge(data, k, pagesize):
p('{}-way merge, initial page size = {}'.format(k, pagesize))
###
### INSERT YOUR OWN CODE
###
If you have implemented it correctly, if you run the code below, you should see the following output.
In [31]:
import random
random.seed(1999)
n = 23
data = [random.randint(1, 100) for _ in range(n)]
sorted_data = multiway_merge(data, 3, 2)
print(sorted_data)
print()
sorted_data = multiway_merge(data, 2, 2)
print(sorted_data)
In [ ]:
In [ ]:
In [ ]: