What matters is whether root must be the first partition, or whether the BIOS BOOT and EFI partitions must be the last? And why?
I did some tests and learned that for legacy boot the partition numbering is what really matters, which your sort changed.
Run grub-install /dev/sda and you should no longer have any problem.
The BIOS GRUB partition contains the number of the partition that holds grub.cfg, so if it changes you need to reinstall GRUB to update that number.
Example on a bare‑metal system with Debian 12 and grub.cfg in /dev/sda2:
# sudo python3 - "$(lsblk -nro PATH,PARTTYPE | awk '$2=="21686148-6449-6e6f-744e-656564454649"{print $1; exit}')"
import lzma, re, struct, sys
dev = sys.argv[1]
data = open(dev,'rb').read()
comp, uncomp = struct.unpack_from('<II', data, 520)
flt = [{"id": lzma.FILTER_LZMA1, "lc":3, "lp":0, "pb":2, "dict_size":1<<26}]
for off in range(512, 16384):
try:
d = lzma.LZMADecompressor(format=lzma.FORMAT_RAW, filters=flt)
out = d.decompress(data[off:off+comp+4096], max_length=uncomp)
except lzma.LZMAError:
continue
if len(out) == uncomp:
break
else:
raise SystemExit("core.img payload not found in " + dev)
m = re.findall(rb'\((?:hd[0-9]+)?,[a-z0-9_]+\)[\x21-\x7e]*', out)
print("BIOS boot partition:", dev)
print("embedded prefix:", b' '.join(m).decode() if m else "none found")
EOF
BIOS boot partition: /dev/sda1
embedded prefix: (,gpt2)/grub
If you run sort again, you can run this command before grub-install and afterwards you should see the number after gpt change.
I forgot to run update-grub, so I did it thinking it would fix the problem, but nope
That command only regenerates grub.cfg. Your issue was upstream, in the image that GRUB embeds in the BIOS GRUB partition, because it can no longer find your grub.cfg.