C game: fastest way to sort 2d objects by distance

Sorting the 2d objects in my SunRacer game took 6300 counts with QuickSort. It was strange to me that a nearly sorted array was not sorted any faster. So I went to look for a better sort algorithm.
At this moment, I'm using the bucket sort algorithm, and sort each bucket with the insertion sort algorithm. Sorting the objects now take 185 counts according the SDL2 performance counter.

More details:
In my game, objects can have a distance from 0 to 1000.
I created 40 buckets and move all objects in one of these 40 buckets. This way, I have 40 small buckets with objects which are near to eachother. Sorting these buckets is faster because there are not many objects in each bucket. Insertion sort becomes slow on big arrays (50+ elements). My buckets are max. 50 elements.

The fastest way to place objects in a bucket is to compare each time with the half of the remaining buckets.

if (element->distance < 500) {
  if (element->distance < 250) { ... }
  else { .... }
} else {
  if (element->distance < 750) { ... }
  else { ...  }
}