Como seccionar registros?

En una tabla tengo 500 registros cuyos estos pertenecen a distintas categorías:
-categoria1
-categoria2
-categoria3
Que algoritmo se debería implementar para que este se liste de la siguiente forma:

Código HTML :

<ul class="categoria1">
 <li>Registro 1</li>
 <li>Registro 2</li>
 <li>Registro 3</li>
 <li>Registro 4</li>
</ul>
<ul class="categoria2">
 <li>Registro 5</li>
 <li>Registro 6</li>
 <li>Registro 7</li>
 <li>Registro 8</li>
</ul>
<ul class="categoria3">
 <li>Registro 9</li>
 <li>Registro 10</li>
 <li>Registro 11</li>
 <li>Registro 12</li>
</ul>

Teniendo en cuenta que en el futuro se pueden agregar mas categorías y estas no son fijas.

pues lo mas logico es hacer una consulta y un bucle en las categorias, luego en ese bucle hacer otra consulta sql, y hacer un bucle ahi adentro con los registros,esa seria la teoria ahora la practica la tendras que ponerla tu o algun otro usuario ,talvez ay alguna forma mas eficiente de realizarlo

No es más que un ORDER BY `categoria` en la consulta SQL.