Por ejemplo...
Si tuviéramos un campo para cálculos temporales que permitiera decimales y hacemos que su valor sea el mismo que su prioridad para cada registro, cuando queramos asignar a un registro una posición, le pondríamos en ese campo temporal la misma prioridad menos 0.5
Temporal = nueva_prioridad - 0,5
Luego reordenamos de nuevo por el valor temporal y reasignamos las prioridades desde la primera hasta llegar a la posición más bajade los registros que se encuentren entre los dos valores de prioridad del registro modificado (bien fuera esta la inicial o la nuevael valor antiguo y el nuevo).
Según tu ejemplo:
Si a 1 le asignamos 3, le ponemos 2.5. Reordenamos y tenemos primero a 2, después a 3 y por último a 1.
Si quisiéramos subir 2 a prioridad 1, le asignamos 0.5 y reordenamos, quedando 2 primero, 1 segundo y 3 tercero.
Y así...
Imagino que hay muchas otras formas de enfocar y solucionar este algoritmo. Esta sería una de ellas.
Espero que te sirva.
Nota: tras cada reordenación volvemos a aaignar a temporal el valor acrualizado de prioridad, volviendo a ser enteros todos de nuevo.