Binary Radix Sort implementation on linked list

Question

I am trying to implement binary radix sort in C which sorts a linked list of integers stably. Although my algorithm has a time complexity of O(log2(k).n) (where k is the biggest integer in the linked list), other standard implementations of algorithms like merge sort/quick sort seem to have better execution time even when input size is large (n>10^6) and kis small (k<1000). Am I doing something wrong which is causing these longer execution times? Could you review this code?

Here is the code for my implementation:

#include<stdio.h> #include<math.h> #include<stdlib.h> #include<time.h> struct ListNode { int val; struct ListNode *next; }; void print_list(struct ListNode *node) // printing integer values of linked list { while(node!=NULL) { printf("%d, ", node->val); node=node->next; } } int getMax(struct ListNode *node) // finding biggest integer in linked list { int max=node->val; while(node!=NULL) { if(node->val > max) { max=node->val; } node=node->next; } return max; } void addMin(struct ListNode *node, int min) // Adding smallest integer in linked list so that no integer in linked list is negative { while(node!=NULL) { node->val+=min; node=node->next; } } void subMin(struct ListNode *node, int min) // returning linked list to original values after sorting { while(node!=NULL) { node->val-=min; node=node->next; } } int getMin(struct ListNode *node) // finding smallest integer in linked list { int min=node->val; while(node!=NULL) { if(node->val < min) { min=node->val; } node=node->next; } return min; } void binarySort(struct ListNode **head, int bit) // sorts linked list based on a particular bit { struct ListNode *temp = *head; struct ListNode *insertNode = *head; struct ListNode *prevNode = NULL; int flag=0; int flag2=0; if((((*head)->val) & (1 << (bit - 1)))) { flag=1; } while(temp!=NULL) { if(flag==0 && !((temp->val) & (1 << (bit - 1)))) { if((temp->next)!=NULL && (((temp->next)->val) & (1 << (bit - 1)))) { insertNode=temp; flag=1; flag2=1; } } else if(flag2==0 && !((temp->val) & (1 << (bit - 1)))) { prevNode->next=temp->next; temp->next=*head; insertNode=temp; *head=temp; temp=prevNode; flag=1; flag2=1; } else if(!((temp->val) & (1 << (bit - 1)))) { prevNode->next=temp->next; temp->next=insertNode->next; insertNode->next=temp; insertNode=temp; temp=prevNode; } prevNode=temp; temp=temp->next; } } struct ListNode* sortList(struct ListNode* head) // binary radix sort { if(head==NULL) { return NULL; } int min=getMin(head); if(min<0) { subMin(head, min); } int biggest_int_len = log2(getMax(head))+1; int i; for(i=1 ; i<=biggest_int_len ; i++) { binarySort(&head, i); } if(min<0) { addMin(head, min); } return head; } int main() // code to test the function { srand(time(0)); int num; struct ListNode *head = (struct ListNode*) malloc(sizeof(struct ListNode)); head->next=NULL; printf("Enter input size: "); scanf("%d", &num); head->val=rand()%1000; struct ListNode *prevNode = head; while(num-1>0) { struct ListNode *temp = (struct ListNode*) malloc(sizeof(struct ListNode)); temp->val=rand()%1000; temp->next=NULL; prevNode->next=temp; prevNode=temp; num--; } printf("\n\n"); print_list(head); clock_t t; t = clock(); struct ListNode *sortedList=sortList(head); t = clock() - t; double time_taken = ((double)t)/CLOCKS_PER_SEC; // in seconds printf("\n\n"); print_list(sortedList); printf("\n\nfun() took %f seconds to execute \n", time_taken); } 

Also is there a good way to test how much memory the sort uses?

Answer 1

• Performance

  The root cause is a poor referential locality. As sorting progresses, and the nodes get relinked, they become accessed in no particular order, all over the memory. This results in too many cache misses, and a cache miss is very expensive.

• binarySort is a bit too complicated. It is very hard to follow. Things like flag, and flag2, (what do they signify?) are always a signal of an unclear design.

  It seems that those flags stem from the special-casing a head node. Try to avoid special cases. Usually having a dummy node greatly simplifies the design. Consider (untested)

   void binarySort(struct ListNode ** head, int bit) { struct ListNode dummy = { .next = *head }; struct ListNode *base = &dummy; struct ListNode *prev = base; struct ListNode *curr = prev->next; while (curr != NULL) { if (!bit_is_set(curr->val, bit)) { prev->next = curr->next; curr->next = base->next; base = curr; } else { prev = prev->next; } curr = prev->next; } *head = dummy.next; }