void Quicksort(CELL **head,CELL **tail,char *pv){
  int x;
  CELL *p,*k;
    p = *head;
    k = *tail;
  for(;;){
    
    x = strcmp(pv,p->id_number);
    if(x < 0){
      for(;;){
        x = strcmp(pv,k->id_number);
        if(x > 0){
          break;
        }
        else
          k = k->prev;        
      }
    }
    else
      p = p->next;
  }
}

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

#define N 20

typedef struct cell {
  struct cell *prev;
  struct cell *next;
  char *id;
} CELL;

CELL *push_front(CELL *x, CELL *y)
{
  if (x != NULL) {
    x->prev = y;
    y->next = x;
  }
  return y;
}

CELL *append(CELL *x, CELL *y)
{
  CELL *p = x;
  /* x を全長に渡って走査するので、改良の余地あり。出来ればxのtailを覚えておければ。 */

  if (y == NULL) return x;
  if (p == NULL) return y;
  while (p->next != NULL) p = p->next;
  p->next = y;
  y->prev = p;
  
  return x;
}

CELL *quicksort(CELL *x)
{
  CELL *c, *i, *j, *k, *t;
  
  /* *xが空か既に単一セルなら戻る */
  if (x == NULL || x->next == NULL) return x;
  else c = x->next;
  
  /* x を単一セルとして切り落とす(先頭のセルをピボットとする) */
  x->prev = x->next = NULL;
  c->prev = NULL;
  k = c;

  /* xより小さいidを持つセルをi, 大きいidを持つセルをjに分ける */
  i = j = NULL;
  while (c != NULL) {
    /* c を単一セルとして切り落とす */
    if (c->next == NULL) 
      t = NULL;
    else {
      t = c->next;
      c->next->prev = NULL;
      c->next = NULL;
    }
    if (strcmp(c->id, x->id) < 0) i = push_front(i, c);
    else if (strcmp(c->id, x->id)) j = push_front(j, c);
    else push_front(x, c);
    c = t;
  }
  /* i, j を更にquicksortする */
  i = quicksort(i); j = quicksort(j);
  /* i, x, j の順につなげる */
  i = append(i, x);
  i = append(i, j);
  
  return i;
}

int main(void)
{
  CELL cl[N], *p;
  int i, j;
  char s[11];
  
  srand((unsigned)time(NULL));
  
  /* リストの初期化を楽するため配列を使っている */
  for (i = 0; i < N; i++) {
    for (j = 0; j < 10; j++) s[j] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[rand() % 36];
    s[10] = '\0';
    cl[i].id = strdup(s);
    if (i == 0) {
      cl[i].prev = NULL;
      cl[i].next = &cl[i + 1];
      cl[i + 1].prev = &cl[i];
    } else if (i == N - 1) {
      cl[i].prev = &cl[i - 1];
      cl[i].next = NULL;
    } else {
      cl[i].next = &cl[i + 1];
      cl[i].prev = &cl[i - 1];
    }
  }

  printf("before quick sort: ");
  for (p = &cl[0]; p != NULL; p = p->next)
    printf("%s ", p->id);
  putchar('\n');
    
  p = quicksort(&cl[0]);
    
  printf("\nafter quick sort: ");
  for (; p != NULL; p = p->next)
    printf("%s ", p->id);
  putchar('\n');

  for (i = 0; i < N; i++) free(cl[i].id);
  
  return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node {
    char *data;
    struct Node *next;
} Node;

Node *quick_sort(Node *p)
{
    Node *v = p, *a = p, *b = NULL, *next;

    if (p == NULL || p->next == NULL) return p;
    next = p->next;
    a->next = NULL;
    while (p = next) {
        next = p->next;
        if (strcmp(p->data, v->data) <= 0)
            p->next = a, a = p;
        else 
            p->next = b, b = p;
    }
    a = quick_sort(a);
    v->next = quick_sort(b);
    return a;
}

Node *create_node(Node *lp, const char *data)
{
    Node *p = malloc(sizeof(Node));
    if (p == NULL || (p->data = strdup(data)) == NULL)
        puts("out of memory"), exit(1);
    p->next = lp;
    return p;
}

void print_list(const Node *p)
{
    for (; p; p = p->next) puts(p->data);
}

int main(void)
{
    char buf[256];
    Node *root = NULL;

    while (scanf("%s", buf) == 1 && buf[0] != '.')
        root = create_node(root, buf);
    root = quick_sort(root);
    puts("---");
    print_list(root);
    return 0;
}

Node *v = p, *a = p, *b = NULL, *next;  を
Node *v = p, *a = NULL, *b = NULL, *next;　に、

a->next = NULL;  を  v->next = NULL; に変更し、

a = quick_sort(a); の後に次の２行を追加。

      for (p = a; p->next; p = p->next) ;
      p->next = v;

Node *quick_sort(Node *p)
{
    Node *v = p, *a = NULL, *b = NULL, *next;

    if (p == NULL || p->next == NULL) return p;
    next = p->next;
    v->next = NULL;
    while (p = next) {
        next = p->next;
        if (strcmp(p->data, v->data) <= 0)
            p->next = a, a = p;
        else 
            p->next = b, b = p;
    }
    if (a) {
        a = quick_sort(a);
        for (p = a; p->next; p = p->next) ;
        p->next = v;
    } else
        a = v;
    v->next = quick_sort(b);
    return a;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node {
    char *data;
    struct Node *next;
} Node;

int compare(const void *a, const void *b)
{
    return strcmp((**(Node**)a).data, (**(Node**)b).data);
}

int main(void)
{
    Node dummy = {0}, *p = &dummy;
    char buf[256];
    int i, cnt;

    for (cnt = 0; scanf("%s", buf) == 1; cnt++) {
        p = p->next = malloc(sizeof(Node));
        if (p == NULL || (p->data = strdup(buf)) == NULL)
            puts("out of memory"), exit(1);
    }
{
    Node *w[cnt];
    for (i = 0, p = dummy.next; p; p = p->next)
        w[i++] = p;
    qsort(w, cnt, sizeof(Node*), compare);
    for (p = &dummy, i = 0; i < cnt; i++)
        p = p->next = w[i];
}
    for (p = dummy.next; p; p = p->next)
        puts(p->data);
    return 0;
}

そのプログラムは偶然に動いていたようです。

1. 最後の要素の next がたまたま NULL だった。
2. ソート後の最後の要素がたまたま初めから最後にあった。
3. 1以上のデータでテストした。(これは良く分かりませんが)

ちなみにテストデータは C のソースコードでやったので、最後の要素は "}" なので
かなりの偶然で動いていたようです。

追加した所に空のコメントを書いておきました。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node {
    char *data;
    struct Node *next;
} Node;

int compare(const void *a, const void *b)
{
    return strcmp((**(Node**)a).data, (**(Node**)b).data);
}

int main(void)
{
    Node dummy = {0}, *p = &dummy;
    char buf[256];
    int i, cnt;

    for (cnt = 0; scanf("%s", buf) == 1; cnt++) {
        p = p->next = malloc(sizeof(Node));
        if (p == NULL || (p->data = strdup(buf)) == NULL)
            puts("out of memory"), exit(1);
    }
    p->next = NULL;  /**/
    if (cnt > 0){  /**/
        Node *w[cnt];
        for (i = 0, p = dummy.next; p; p = p->next)
            w[i++] = p;
        qsort(w, cnt, sizeof(Node*), compare);
        for (p = &dummy, i = 0; i < cnt; i++)
            p = p->next = w[i];
        p->next = NULL;  /**/
        for (p = dummy.next; p; p = p->next)
            puts(p->data);
    }
    return 0;
}

>        Node *w[cnt];