Ftyjtk

The code bellow is my implementation for the natural merge exercise in Robert Sedgwick's Algorithms book:

Write a version of bottom-up mergesort that takes advantage of order
in the array by proceeding as follows each time it needs to find two
arrays to merge: find a sorted subarray (by incrementing a pointer
until finding an entry that is smaller than its predecessor in the
array), then find the next, then merge them.

def merge(a, lo, mi, hi):

    aux_lo = deque(a[lo:mi])

    aux_hi = deque(a[mi:hi])

    # this takes more space than allowed



    for i in range(lo, hi):

        if len(aux_lo) and len(aux_hi):

            a[i] = aux_lo.popleft() if aux_lo[0] < aux_hi[0] else aux_hi.popleft()

        elif len(aux_lo) or len(aux_hi):

            a[i] = aux_lo.popleft() if aux_lo else aux_hi.popleft()



def find_next_stop(a, start):

    if start >= len(a)-1:

        return start



    stop = start + 1

    if a[start] < a[stop]:

        while(stop<len(a)-1 and a[stop] <= a[stop+1]):

            stop += 1

    else:

        while(stop<len(a)-1 and a[stop] >= a[stop+1]):

            stop += 1



        _stop = stop

        while(start<_stop):

            a[_stop], a[start] = a[start], a[_stop]

            start += 1

            _stop -= 1

    return stop



def natural_merge(a):

    lo = hi = 0

    while(True):

        lo = hi

        mi = find_next_stop(a, lo)

        if lo == 0 and mi == len(a) - 1:

            return

        hi = find_next_stop(a, mi)

        if mi == hi == len(a)-1:

            lo = hi = 0

            continue

        merge(a, lo, mi, hi)

I take this anwser as a reference.

Tests and bugs

Your code looks mostly good. Before trying to go and change the code to see what can be improved. I usually try to write a few simple tests. This is even easier when you have a reference implementation that can be compared to your function. In your case, I wrote:

TESTS = [

    ,

    [0],

    [0, 0, 0],

    [0, 1, 2],

    [0, 1, 2, 3, 4, 5],

    [5, 4, 3, 2, 1, 0],

    [5, 2, 3, 1, 0, 4],

    [5, 2, 5, 3, 1, 3, 0, 4, 5],

]



for t in TESTS:

    print(t)

    ref_lst, tst_lst = list(t), list(t)

    ref_lst.sort()

    natural_merge(tst_lst)

    print(ref_lst, tst_lst)

    assert ref_lst == tst_lst

which leads to a first comment: the empty list is not handled properly and the function never returns.

Improving merge

The case elif len(aux_lo) or len(aux_hi) seems complicated as we check if aux_lo just after. Things would be clearer if we were to split in two different cases:

    if len(aux_lo) and len(aux_hi):

        a[i] = aux_lo.popleft() if aux_lo[0] < aux_hi[0] else aux_hi.popleft()

    elif len(aux_lo):

        a[i] = aux_lo.popleft()

    elif len(aux_hi):

        a[i] = aux_hi.popleft()

Also, we could reuse the fact that in a boolean context, list are considered to be true if and only if they are not empty to write:

for i in range(lo, hi):

    if aux_lo and aux_hi:

        a[i] = aux_lo.popleft() if aux_lo[0] < aux_hi[0] else aux_hi.popleft()

    elif aux_lo:

        a[i] = aux_lo.popleft()

    elif aux_hi:

        a[i] = aux_hi.popleft()

Improving find_next_stop

You don't need so many parenthesis.

You could store len(a) - 1 in a variable in order not to re-compute it every time.

The name _stop is pretty ugly. I do not have any great suggestion for an alternative but end seems okay-ish.

More tests... and more bugs

I wanted to add a few tests to verify an assumption... and I stumbled upon another issue.

Here is the corresponding test suite:

TESTS = [

    ,

    [0],

    [0, 0, 0],

    [0, 1, 2],

    [0, 1, 2, 3, 4, 5],

    [5, 4, 3, 2, 1, 0],

    [0, 1, 2, 2, 1, 0],

    [0, 1, 2, 3, 2, 1, 0],

    [5, 2, 3, 1, 0, 4],

    [5, 2, 5, 3, 1, 3, 0, 4, 5],

    [5, 2, 5, 3, 1, 3, 0, 4, 5, 3, 1, 0, 1, 5, 2, 5, 3, 1, 3, 0, 4, 5],

]