My idea to solve your problem is to use quick sort to sort your list simply chained.

To do this, I'm going to use a impl_comp function that will compare two elements of the list (the data will be passed, not the list nodes). impl_comp can then be implemented to compare any two data you want, as in the case it is string, we will use strcmp below.

Quick sort

Quick sort is a recursive algorithm that is based on the selection of a pivot, the data partition and the recursive ordering of that partition.

Your algorithm is:

quicksort(tlista *lista):
    elemento pivô = seleciona_pivô(lista)
    tlista *menor, *maiorigual
    partição(lista, pivô, &menor, &maiorigual)
    menor = quicksort(menor)
    maiorigual = quicksort(maiorigual)
    se pivô faz parte da lista, e não foi inserido no maiorigual:
        apendar elemento pivô no final de menor
    apendar maiorigual no final de menor
    retorne menor

partição(tlista *lista, elemento pivô, tlista **menor_retorno, tlista **maiorigual_retorno):
    tlista *atual = lista
    tlista *menor_cauda = nulo
    tlista *maiorigual_cauda = nulo
    enquanto atual != nulo:
        tlista *próximo = lista->próximo
        atual->próximo = nulo
        se impl_cmp(atual->valor, pivô) < 0:
            // inserir na partição menor
            se menor_cauda == nulo:
                menor_cauda = atual
                *menor_retorno = menor_cauda
            senão:
                 menor_cauda->próximo = atual
                 menor_cauda = atual
       senão:
            // inserir na partição maior ou igual
            se maiorigual_cauda == nulo:
                maiorigual_cauda = atual
                *maiorigual_retorno = maiorigual_cauda
            senão:
                 maiorigual_cauda->próximo = atual
                 maiorigual_cauda = atual
        atual = próximo

Runtime

It has mean execution time in the order of o(n log n) , and is therefore comparable with other linear (log times) algorithms such as merge sort and heap sort: as this notation is asymptotic, representing only the dominant behavior of the runtime function, does not take into account minor order terms, nor does it have any constant multiplying the dominant term.

According to Wikipedia, the runtime of the merge sort can be 3 times faster in the average case . In the worst case, quick sort requires o(n^2) operations to run. Other quadratic time functions are insertion sort, selection sort and bubble sort.

Stability

Another interesting point to mention is that quick sort is not a stable ordering method . A stable ordering maintains the relative position of elements of the same weight; for example, if we were to sort alphabetically, ignoring the case, and had as input "ana", "jeff", "Ana" , a stable sort would necessarily produce "ana", "Ana", "jeff" , but perhaps the output of quick sort is "Ana", "ana", "jeff" .

Knowing if ordinances are stable is interesting when you want to organize by multiple distinct factors. A case of this sort of ordering could be applied here in the Stack Overflow in Portuguese (didactic example, not necessarily practical): order people by order of points and, in case of a tie, prioritize the most recent ones.

To perform this ordering, we could use a sort order for more recent and then a stable ordering by points; as we first ordered by more recent ones, stable ordering will keep this partial order in order to do the final ordering.

And this game in C, how is it?

First, I want to build with a level of abstraction here. Where I put elemento switch to the type actually being used. In the present case, it would be char* , because it is a string comparison. Secondly, I'm postponing the implementation of impl_cmp(elemento a, elemento b) so that you can use the proper implementation of comparison.

/* substitua "elemento" pelo tipo de dado utilizado */
typedef struct lista {
    elemento valor;
    struct lista *prox;
} tlista;

/* não se esqueça de implementar essa função */
int impl_cmp(elemento a, elemento b);

/* l_ret: retorno menor/lesser
 * ge_ret: retorno maior ou igual/greater equal
 */
void partition(tlista *lista, elemento pivot, tlista **l_ret, tlista **ge_ret) {
    tlista *l_tail = NULL;
    tlista *ge_tail = NULL;

    tlista *atual = lista;

    while (atual != NULL) {
        tlista *prox = atual->prox;

        atual->prox = NULL;
        if (impl_cmp(atual->valor, pivot) < 0) {
            if (l_tail == NULL) {
                 l_tail = atual;
                 *l_ret = l_tail;
            } else {
                l_tail->prox = atual;
                l_tail = atual;
            }
        } else {
            if (ge_tail == NULL) {
                 ge_tail = atual;
                 *ge_ret = ge_tail;
            } else {
                ge_tail->prox = atual;
                ge_tail = atual;
            }
        }
        atual = prox;
    }
}

tlista *concatena_3_listas(tlista *a, tlista *b, tlista *c) {
    tlista *head = a;
    tlista *tail = head;

    if (head != NULL) {
        head = tail = b;
    } else {
        while (tail->prox != NULL)  {
            tail = tail->prox;
        }
        tail->prox = b;
    }

    if (head != NULL) {
        head = tail = c;
    } else {
        while (tail->prox != NULL)  {
            tail = tail->prox;
        }
        tail->prox = c;
    }

    return head;
}

tlista *quicksort(tlista *lista) {
    /* vou pegar como pivot sempre o primeiro da lista, removendo-o de lá; poderia usar outra técnica, mas essa é boa o suficiente para o exemplo */
   tlista *pivot_lista = lista;
   elemento pivot = pivot_lista->valor;

   lista = lista->prox;
   pivot_lista->prox = NULL;

   tlista *menor, *maior;

   menor = maior = NULL;

   partition(lista, pivot, &menor, &maior);

   menor = quicksort(menor);
   maior = quicksort(maior);

  return concatena_3_listas(menor, pivot_lista, maior);
}

Notes on comparison with implementation over vector

When you use quicksort in loco in a vector, the beginning and end of each set of elements in the recursive partition and quicksort calls are always sent to the recursive functions. Also, when the pivot is part of the vector, we make a last swap of the last element of the sub-element of smaller elements with the pivot (which usually stays in the first position of the vector, it is exchanged with the first element of the sub-element of greater or equal elements).

As the simply linked list data structure carries with it the notion of beginning (the list pointer is the beginning of itself) and end (last existing element whose next element is null), it is not necessary to pass this information forward.

You need two loops to work, the algorithm is bubble sort;

void ordenar(lista **l) {

    if(*l == NULL || (*l)->prox == NULL) return; //se for nulo(vazio), ou apenas 1 elemento
    lista *aux = *l, *t;
    char s[100]; //precisa de espacao suficiente para armazenar o nome

    while(aux != NULL) {
      t = aux->prox;
      while(t != NULL) {
        if(strcmp(aux->nome, t->nome) > 0) { //se vir depois
            strcpy(s, aux->nome);
            strcpy(aux->nome, t->nome);
            strcpy(t->nome, s);
        }
        t = t->prox;
      }
      aux = aux->prox;
    }
}

link