[aguml]

Bueno, el uso de una lista auxiliar no era eficiente porque hay varias iteraciones y por el uso doble de memoria así que despues de mucho darle vueltas y mucha ayuda para entender como hacerlo con punteros he conseguido hacerlo intercambiando los punteros de la lista:

Código PHP:

//Intercambia el contenido de dos elementos de la lista y nos devuelve el puntero al primero
//Hay que hacer que los punteros sig apunten adonde deben ya que si no es así la lista se
//rompería. Para eso uso sigAux para, una vez intercambiados los elementos, intercambiar
//sus punteros sig
Elemento * Swap(Elemento *primero, Elemento *segundo)
{
   Elemento *aux, *sigAux;

   aux = primero;
   sigAux = segundo->sig;
   primero = segundo;
   segundo = aux;
   segundo->sig = sigAux;
   primero->sig = segundo;

   return primero;
}
//-----------------------------------------------------------------------------

//Ordena el contenido de la lista
void OrdenarLista(Lista *lista)
{
   int i,j;
   Elemento *actual, *anterior;

   for (i=1; i < lista->nElementos; i++)
   {
      for (j=0, actual = lista->inicio, anterior = NULL; j < lista->nElementos-(i); j++, actual = actual->sig)
      {
         if (actual->indice >= actual->sig->indice)
         {
            //Si el elemento actual es el primero de la lista pongo al que apunta el puntero
            //sig del actual como inicio ya que serán intercambiados
            if(actual == lista->inicio)
               lista->inicio = actual->sig;

            //Si el puntero sig de actual es el mismo que el fin de la lista pongo al actual
            //como fin ya que voy a intercambiarlos
            if(actual->sig == lista->fin)
               lista->fin = actual;

            //Intercambio los elementos
            actual = Swap(actual,actual->sig);

            //Si anterior es igual a NULL será porque actual es el primer elemento de la lista
            //y por lo tanto no existe un elemento anterior
            //Si no es NULL actualizo el puntero sig del elemento anterior al nuevo elemento
            //actual despues del intercambio
            if(anterior != NULL)
               anterior->sig = actual;
         }
         //Guardo el puntero al elemento actual para la siguiente pasada
         anterior = actual;
      }
   }
} 


Espero que al menos le sirva a alguien tanto esfuerzo jejeje.