Como acabei de ler, o ALTER TABLE ... ORDER BY ... query é útil para melhorar o desempenho em determinados cenários. Estou surpreso que o Índice PK não ajude com isso. Mas, dos dos documentos do MySQL , parece que o InnoDB faz usar o índice. No entanto, o InnoDB tende a ser mais lento que o MyISAM. Dito isto, com o InnoDB você não precisaria reordenar a tabela, mas perderia a velocidade incrível do MyISAM. Ainda pode valer a pena tentar.

Da maneira como você explica os problemas, parece que há muitos dados carregados na memória (talvez haja até trocas acontecendo?). Você pode verificar isso facilmente monitorando o uso da memória. É difícil dizer, pois não conheço o MySQL muito bem.

Por outro lado, acho que seu problema está em um lugar muito diferente:você está usando uma máquina com apenas 512 Megas de RAM como servidor de banco de dados com uma tabela contendo mais de 4 milhões de linhas... operação em toda a mesa dessa máquina. Parece que 512Megs não serão suficientes para isso.

Uma questão muito mais fundamental que estou vendo aqui:você está desenvolvendo (e provavelmente testando também) em um ambiente que é muito diferente do ambiente de produção. O tipo de problema que você está explicando é esperado. Sua máquina de desenvolvimento tem seis vezes mais memória que sua máquina de produção. Acredito que posso dizer com segurança que o processador também é muito mais rápido. Nesse caso, sugiro que você crie uma máquina virtual imitando seu site de produção. Dessa forma, você pode testar facilmente seu projeto sem interromper o local de produção.