# Implementation of merge sort that takes sublinear extra space

I implemented an algorithm that takes only sublinear extra space as required in the exercise description:

Develop a merge implementation that reduces the extra space requirement to max(M, N/M). (dividing the array into N/M blocks of size M).

def insert_sort(a, lo, hi):
for i in range(lo+1, hi):
j = i
while(j>lo and a[j]<a[j-1]):
a[j], a[j-1] = a[j-1], a[j]
j -= 1

def in_place_merge(a, lo, mi, hi):
aux_hi = a[mi:hi]

for i in reversed(range(lo, hi)):
if aux_hi:
last_a = i - len(aux_hi)
if (last_a < lo or aux_hi[-1] > a[last_a]):
a[i] = aux_hi.pop()
else:
a[i] = a[last_a]
else:
break

def block_insertion_sort(a):
M = 5
for i in range(0, len(a), M):
insert_sort(a, i, min(i+M, len(a)))
if i > 0:
in_place_merge(a, 0, i, min(i+M, len(a)))


In addition, I don't understand the max(M, N/M) part, then I don't know if I have made it. Any suggestions are highly appreciated.

• Could you provide the tests?
– vnp
Dec 18 '18 at 4:47
• @vnp What do you mean by tests? The test code for every function? Dec 18 '18 at 12:07