List indexing problem

Python Help
1

In the following sorting code, when we replace len(y)-i-1 with -i-1, we get a different result.

def f(x,y):
	if not x:
		return y
	for i in range(len(y)):
		if y[u:=len(y)-i-1]<=x[-1]:
			return f(y[:u+1],x+y[u+1:])
	return x+y
def g(x):
	if len(x)<=1:
		return x
	return f(g(x[:len(x)//2]),g(x[len(x)//2:]))
print(g([7,5,11,1,12]))

While they should be the same because indexing starts from zero at the beginning and indexing starts from -1 at the end.

2

Index go from 0 to len(y)-1 not -1.
So if y is 4 items long the indices are 0, 1, 2, 3.
Does that help?

3

Slicing with u+1 goes wrong when u is -1.

1 Like
4

Add a few debug print calls to see what changes when you replace len(y)-i-1 with -i-1.

First, let’s add print to your original code. We’ll need to make the input list a little different (insert 1000 in the middle) so it shows the problem.

def f(x,y):
    print(f"{x = } {y = }")
    if not x:
        return y
    for i in range(len(y)):
        if y[u:=len(y)-i-1]<=x[-1]:
            print(f"    {i = }, {u = }, {y[:u+1] = }, {x+y[u+1:] = }")
            return f(y[:u+1],x+y[u+1:])
    return x+y
def g(x):
    if len(x)<=1:
        return x
    return f(g(x[:len(x)//2]),g(x[len(x)//2:]))
print(g([7, 5, 11, 1000, 1, 12]))

This is what it outputs:

x = [5] y = [11]
x = [7] y = [5, 11]
    i = 1, u = 0, y[:u+1] = [5], x+y[u+1:] = [7, 11]
x = [5] y = [7, 11]
x = [1] y = [12]
x = [1000] y = [1, 12]
    i = 0, u = 1, y[:u+1] = [1, 12], x+y[u+1:] = [1000]
x = [1, 12] y = [1000]
x = [5, 7, 11] y = [1, 12, 1000]
    i = 2, u = 0, y[:u+1] = [1], x+y[u+1:] = [5, 7, 11, 12, 1000]
x = [1] y = [5, 7, 11, 12, 1000]
[1, 5, 7, 11, 12, 1000]

Now let’s replace len(y)-i-1 with -i-1:

def f(x,y):
    print(f"{x = } {y = }")
    if not x:
        return y
    for i in range(len(y)):
        if y[u:=-i-1]<=x[-1]:
            print(f"    {i = }, {u = }, {y[:u+1] = }, {x+y[u+1:] = }")
            return f(y[:u+1],x+y[u+1:])
    return x+y
def g(x):
    if len(x)<=1:
        return x
    return f(g(x[:len(x)//2]),g(x[len(x)//2:]))
print(g([7, 5, 11, 1000, 1, 12]))

This is the new output:

x = [5] y = [11]
x = [7] y = [5, 11]
    i = 1, u = -2, y[:u+1] = [5], x+y[u+1:] = [7, 11]
x = [5] y = [7, 11]
x = [1] y = [12]
x = [1000] y = [1, 12]
    i = 0, u = -1, y[:u+1] = [], x+y[u+1:] = [1000, 1, 12]
x = [] y = [1000, 1, 12]
x = [5, 7, 11] y = [1000, 1, 12]
    i = 1, u = -2, y[:u+1] = [1000, 1], x+y[u+1:] = [5, 7, 11, 12]
x = [1000, 1] y = [5, 7, 11, 12]
[1000, 1, 5, 7, 11, 12]

You can see that the values of y[:u+1] and x+y[u+1:] are different and the algorithms diverge.