Sorting a linked list

 

 /**Algorithm best suited to sort a linked list. 
  * 
  * Write a C program to implement that algorithm. 
  * Modified quick sort should work. 
  * 
  * ex: 4 8 2 9 5 3 
  *   4 2 8 9 5 3 
  *   4 2 3 9 5 8 
  */ 

 #include "Common.h" 

 typedef struct _node { 
      struct _node *next; 
      int value; 
 } Node; 

 void swap(Node* node1, Node* node2) { 
      int temp = node1->value; 
      node1->value = node2->value; 
      node2->value = temp; 
 } 

 void sortLinkedList(Node *head, Node *lastNode) { 
      if (head == NULL ) 
           return; 

      // if last two nodes and already sorted return 
      if (head == lastNode || head->next == lastNode) 
           return; 

      Node* nextNode = head->next; 
      if (nextNode->next == lastNode) 
      { 
           if (head->value < head->next->value) 
                     return; 
           else 
           { 
                swap(head, head->next); 
                return; 
           } 
      } 

      Node *pivot = head; 
      Node *startNode = head->next, *endNode = head->next, 
           *currSwapNode = startNode;

      while (1) { 
           while (startNode != lastNode) { 
                if (startNode->value < pivot->value) { 
                     currSwapNode = startNode; 
                     startNode = startNode->next; 
                } else { 
                     break; 
                } 
           } 

           if (startNode == lastNode) 
                break; 
           endNode = startNode == lastNode ? startNode : startNode->next; 

           while (endNode != lastNode && endNode->value >= pivot->value) { 
                endNode = endNode->next; 
           } 

           if (endNode != lastNode && startNode != lastNode) 
           { 
                swap(startNode, endNode); 
                currSwapNode = startNode; 
           } 
           else 
                break; 

           startNode = startNode->next; 
      } 

      if (currSwapNode != NULL && pivot->value > currSwapNode->value) { 
           swap(pivot, currSwapNode); 
           sortLinkedList(head, currSwapNode); 
           sortLinkedList(currSwapNode->next, lastNode); 
      } 
      else 
           sortLinkedList(currSwapNode, lastNode); 
 } 

 int main() { 
      int numNumbers, number, i; 
      Node *head = NULL, *current = NULL; 
      printf("Enter the numbers : "); 
      scanf("%d", &numNumbers); 

      for (i = 0; i < numNumbers; i++) { 
           scanf("%d", &number); 
           Node *node = malloc(sizeof(Node)); 
           node->value = number; 
           node->next = NULL; 
           if (current != NULL ) { 
                current->next = node; 
           } 

           if (head == NULL ) { 
                head = node; 
           } 
           current = node; 
      } 

      current = head; 
      while (current != NULL ) { 
           printf("%d ", current->value); 
           current = current->next; 
      } 

      printf("\n"); 
      sortLinkedList(head, NULL ); 

      current = head; 
      while (current != NULL ) { 
           printf("%d ", current->value); 
           current = current->next; 
      } 
      return 0; 
 }