Quick sort using linked list

Hey everyone!
I've been trying to implement a quick sort algorithm for linked list but when i try to run it with 1000000 values my compiler tells me its running too long and ends up not finishing. However when i run it with 10 values it seems to work fine.
Is there anyway to improve this run time?

Code:

struct listnode *quicksort( struct listnode *data ) {
   size_t length = 0;
   struct listnode *pivNode, *temp = NULL, *low = NULL, *high = NULL, *ltail = NULL, *htail = NULL, *prev = NULL, *end = NULL, *next;

   // Get length
   for( struct listnode *cursor = data; cursor != NULL; cursor = cursor->next ) {
      length++;
   }

   // Base case
   if( length <= 1 ) { return data; }

   // Get and remove pivot from data
   pivNode = data;
   for( int i = 0; i < rand()%length; i++ ) {
      pivNode = pivNode->next;
   }

   for( struct listnode *cursor = data; cursor != NULL; cursor = cursor->next ) {
      if( cursor == pivNode ) {
         if( prev == NULL ){
            data = data->next;
         }
         else {
            prev->next = cursor->next;
         }
         break;
      }
      else {
         prev = cursor;
      }
   }

   // Split into low and high
   for( struct listnode *cursor = data; cursor != NULL; cursor = cursor->next ) {
      temp = new struct listnode;
      temp->value = cursor->value;
      temp->next = NULL;
      if( cursor->value < pivNode->value ) {
         if( ltail == NULL ) {
            low = temp;
            ltail = temp;
         }
         else {
            ltail->next = temp;
            ltail = ltail->next;
         }
      }
      else {
         if( htail == NULL ) {
            high = temp;
            htail = temp;
         }
         else {
            htail->next = temp;
            htail = htail->next;
         }
      }
   }
   
   low = quicksort( low );
   high = quicksort( high );

if(low != NULL){
      pivNode->next = high;
      for( struct listnode *cursor = low; cursor != NULL; cursor = cursor->next) {
        if( cursor->next == NULL ) {
          cursor->next = pivNode;
          break;
        }
      }
      return low;   
  }
  else {
     pivNode->next = high;       
     return pivNode;   
  }

What do you mean "my compiler tells me its running too long"? That's not the usual job of the compiler. Perhaps you mean you're running it in an IDE and that's giving you a message?

What does the memory consumption look like as the program runs? From looking at the code I would guess that it's going slowly because it's eating memory.

Where you partition the list into low and high:

Code:

   // Split into low and high
   for( struct listnode *cursor = data; cursor != NULL; cursor = cursor->next ) {
      temp = new struct listnode;
      temp->value = cursor->value;

So - if I'm reading this right, you're creating a new node "temp" for every node, and then building yourself new linked lists by linking the temps together. Is there some way you could do this without creating new nodes? It seems like this will consume a lot of memory. It should be possible to construct the new lists in place out of existing nodes. I guess this'll be a bit trickier, and "trickier" probably means more code and more processing. So you should probably check and see if it is memory that is the problem, or if it's sheer runtime.

If it's just runtime, you might see if you can avoid looping over the whole linked list so many times. Do you really need to loop over the whole lot to count the length every time? Could you not pass that as an argument, having calculated it when you constructed the high/low partitions? Similarely with the pivot node -- you have one loop to identify it and another loop to remove it. Could they be merged into one?

Code:

for( int i = 0; i < rand()%length; i++ )

The rand()%length is evaluated each time through the loop, resulting in a different random number each time. This does not give you an equal chance of selecting each item as the pivot.
Not that it matters a lot of course, since the algorithm will run correctly with any pivot. But you should probably still fix it.

Other than that it looks okay until line 36. Why are you allocating anything at all? It should be a simple matter of popping an item from the original list, and then pushing it onto one of two other lists.
You don't bennfit at all from keeping track of the tails of lists anywhere. The only thing that could help with would be the concatenation of the sorted lists and the pivot afterwards, but you are simply walking through the list again for that.