JavaScript - imagen cargando.. mientras ejecuta otro javascript

Muy Buenas jefes, en una página de asp muestro una tabla que se puede ordenar por columnas. Ya la tengo desarrollada, el problema es que el número de registros a ordenar es elevado (700 u más) así que me gustaría mostrar una imagen animada del tipo cargando... mientras se produce la ordenación.

Desarrollando esto encuentro un problema y es que la imagen no se muestra hasta el final de la ordenación. He observado que si muestro la imagen desde el principio antes de ordenar, la imagen detiene su movimiento mientras se ordenan los campos y luego vuelve a moverse.
¿Podríais ayudarme con este tema? .
¿Cómo puedo hacer para mostrar la imagen en movimiento mientras ordena por javascript las columnas que va pulsando el usuario de la aplicación?

Muchas gracias a todos.

Buenas.

¿Qué tipo de imagen estás usando? ¿Probaste con un gif, que tenga el movimiento que tu quieres?

Sí, probé con un gif animado ajax. Pero como luego sigo ejecutando código javascript la imagen se queda parada (no sigue en movimiento).