Python merge sort in place, so space complexity is O(1)

in-place-merge-sort.py

import random

def merge_sort(xs):
    """Inplace merge sort of array without recursive. The basic idea
    is to avoid the recursive call while using iterative solution. 
    The algorithm first merge chunk of length of 2, then merge chunks
    of length 4, then 8, 16, .... , until 2^k where 2^k is large than 
    the length of the array
    """
    
    unit = 1
    while unit <= len(xs):
        h = 0
        for h in range(0, len(xs), unit * 2):
            l, r = h, min(len(xs), h + 2 * unit)
            mid = h + unit
            # merge xs[h:h + 2 * unit]
            p, q = l, mid
            while p < mid and q < r:
                if xs[p] < xs[q]: p += 1
                else:
                    tmp = xs[q]
                    xs[p + 1: q + 1] = xs[p:q]
                    xs[p] = tmp
                    p, mid, q = p + 1, mid + 1, q + 1

        unit *= 2
    
    return xs
    

def test():
    assert merge_sort([4,3,2,1]) == [1,2,3,4]
    assert merge_sort([4,2,3,1]) == [1,2,3,4]
    assert merge_sort([4,5,3,2,1]) == [1,2,3,4,5]
    
    for _ in range(100):
        tmp = range(100)
        random.shuffle(tmp)
        assert merge_sort(tmp) == range(100)
    
    return 'test pass!'