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

gistfile1.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:
                # use <= for stable merge merge
                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!'

thx, saved me about 30 min if I had to do it myself, this thing isn't striaght forward at all haha!

thx, for the test cases

`
while p < mid and q < r:
if xs[p] <= xs[q]: p += 1 #we should use <= , otherwise it would not be stable

merge_sort([ 2(a), 2(b), 2(c), 3]) = [ 2(c), 2(a), 2(b), 3]`

`
while p < mid and q < r:
if xs[p] <= xs[q]: p += 1 #we should use <= , otherwise it would not be stable

merge_sort([ 2(a), 2(b), 2(c), 3]) = [ 2(c), 2(a), 2(b), 3]`

Thanks for pointing out this. I don't notice about stable sort at first :). Already made the change.