-1
def merge_sort(a):
    if len(a)<=1:
        return a
    left = merge_sort(a[:len(a)//2])
    //print('this is left step {}'.format(left))
    right = merge_sort(a[len(a)//2:])
    //print('this is right step {}'.format(right))
    return merge(left, right)

i understand algebraic recursive functions i understand how it works.

what i dont understand is how merge_sort(a[len(a)//2:]) is getting just one number from the passed in list called 'a' (i have a def create_random_array that passes in random list of numbers ).

my thinking was that it would first split the list in half-witch I could see in my print function, then it would split it again , and again until there is only one that can then be compared.

how does merge_sort(a[len(a)//2:]) work

other part of the code that might be useful to understand my mess


def create_array(size = 5, max = 10):
    from random import randint
    return [randint(0,max) for _ in range(size)]



def merge(a,b):
    c = []
    a_idx = 0
    b_idx = 0
    print(a[a_idx])
    print(b[b_idx])
    while a_idx<len(a) and b_idx<len(b):
        if a[a_idx]<b[b_idx]:
            c.append(a[a_idx])
            a_idx+=1
        else:
            c.append(b[b_idx])
            b_idx+=1
    if a_idx==len(a):
        c.extend(b[b_idx:])
    else:
        c.extend(a[a_idx:])
    return c
anthony pizarro
  • 135
  • 7

1 Answers1

0

... then it would split it again , and again until there is only one that can then be compared.

Yes, because at some point, after halving (and halving, and halving ...) your list then it will call merge_sort with a list of just one item.

And the first thing that function does is this:

def merge_sort(a):
    if len(a)<=1:
        return a

That is, a list of just one item is returned as is (rather than being halved).

donkopotamus
  • 22,114
  • 2
  • 48
  • 60