Looks like the 3x penalty is about right:

  There are 5001834 entries out of 10000000 less than 128
  Exeuction took 65335182 nanoseconds
  There are 5001834 entries out of 10000000 less than 128
  Exeuction took 26693952 nanoseconds

Using the following code I hacked together:

  #include <stdio.h>
  #include <stdlib.h>
  #include <time.h>
  #include <sys/types.h>
  
  #define DATASIZE 10000000
  #define NSEC_PER_SEC 1000000000
  
  int cmp(const void* a, const void* b)
  {
  	return *(unsigned char*)a - *(unsigned char*)b;
  }
  
  int countsmall(unsigned char* data)
  {
  	struct timespec start;
  	struct timespec end;
  	u_int64_t delta;
  	int lcv;
  	int numsmall;
  
  	numsmall = 0;
  	clock_gettime(CLOCK_MONOTONIC, &start);
  	for ( lcv = 0; lcv < DATASIZE; lcv++ )
  		if ( data[lcv] < 128 )
  			numsmall++;
  	clock_gettime(CLOCK_MONOTONIC, &end);
  
  	delta = (end.tv_sec   * NSEC_PER_SEC + end.tv_nsec) - 
  		(start.tv_sec * NSEC_PER_SEC + start.tv_nsec);
  			
  	printf("There are %d entries out of %d less than 128\n", numsmall, DATASIZE);
  	printf("Exeuction took %ld nanoseconds\n", delta);
  
  	return 0;
  }
  
  int main(int argc, char** argv)
  {
  	unsigned char data[DATASIZE];
  	int lcv;
  	srandom(time(NULL));
  	
  	for ( lcv = 0; lcv < DATASIZE; lcv++ )
  		data[lcv] = random();
  
  	countsmall(data);
  
  	qsort(data, DATASIZE, sizeof(unsigned char), cmp);
  
  	countsmall(data);
  
  	return 0;
  }