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()
                a[i] = a[last_a]

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.