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 de los registros que se encuentren entre los dos valores de prioridad del registro modificado (el 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.