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.
