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.