Muchos de los reproductores que existen en el mercado, en especial los más baratos, tienen un problema: al querer reproducir las canciones, no tiene un ordenamiento alfabético, sino que el orden es en función de que canción es grabada primero. Por lo que al terminar de pasar toda nuestra música, quedan las canciones totalmente mezcladas de su orden original, a pesar de usar carpetas para separarlas.

Me enteré gracias a @gadius, de una herramienta para Linux llamada fatsort. Esta herramienta permite, entre otras opciones, re-acomodar las canciones de nuestro MP3 para que sigan un orden alfabético.

Se encuentra en los repositorios de la mayoría de las distribuciones, por lo que luego de instalarla deberás hacer:

fatsort /dev/sXX

Siendo /dev/sXX el dispositivo MP3 que necesites ordenar.

Y con eso tendrás todas tus canciones ordenadas alfabéticamente, respetando la jerarquía de carpetas ya existente. Al probarlo con un total de canciones de 500 MB, no tardó más que un segundo, pero eso dependerá del equipo, puertos USB y reproductor que tengas.