Score: ~4650

def rand_shell(l): steps = [1, 3, 5, 9, 17, 33, 65, 129] candidates = [(left, left + step) for (step, nstep) in zip(steps, steps[1:]) for left in range(0, l - step) for i in range(nstep // step) ] return random.choice(candidates) 

Try it online!

I've no idea why. I just tried sequences listed on wikipedia artical for shellsort. And this one seem works best. It get similar score with the one xor posted.