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;
}
{
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 *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;
insertNode=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;
}
}
{
{
return NULL;
}
if(min<0)
{
}
int i;
for(i=1 ; i<=biggest_int_len ; i++)
{
}
if(min<0)
{
}
}
int main() // code to test the function
{
srand(time(0));
int num;
struct ListNode *head = (struct ListNode*) malloc(sizeof(struct ListNode));
printf("Enter input size: ");
scanf("%d", &num);
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");
clock_t t;
t = clock();
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?

• To handle negative numbers, just add special logic for sign bits (reverse it) may save findMin, subMin, addMin parses. Also, you may avoid find max value first, but know if I'm running last parse in binarySort. In binarySort, maintain 2 linked list and concat them when all values add to some of them would simplify your codes.
– tsh
Feb 1 '21 at 6:31
• Thank you for your suggestions. I will try to implement them. Feb 1 '21 at 20:39

• 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;
}

• Had you ever changed curr in the loop? And maybe the condition curr != NULL will never change and the loop will never finish.
• Typo. Thanks, The cursor shall be curr. Fixed.