What is the fastest simple sorting algorithm (other than quick sort / merge sorting) for 500 numbers?

Question

I would like to implement some sorting algorithm that is fast enough to sort 500 numbers many times (e.g. 300 sort iterations of 500 numbers each)

I don’t like fast sorting, merge sorting, because they are more difficult to implement than sorting bubbles, sorting sorting, sorting insertion.

It’s just interesting that it’s better (simple to implement and with some better complexities more difficult than O (N ² ) if many numbers are already sorted) the simplest sorting algorithm in this case

Sort numbers are a type of doubling.

Answer 1

I once compared some sorting algorithms . I found that comb sorting and heap sorting are very easy to implement and give very good results.

void comb_sort(double *a, int size) { int gap = size; bool swapped = false; while ((gap > 1) || swapped) { if (gap > 1) gap = int(gap/1.247330950103979); swapped = false; for (int i = 0; gap + i < size; i++) if (a[i + gap] < a[i]) { swap(&a[i + gap], &a[i]); swapped = true; } } } 

You can profile several algorithms in your data set and choose the best one for your needs.

EDIT Adding a magic number calculation that I used to sort the comb. I found this in some book (which I no longer remember) a few years ago.

Answer 2

You can use radix collation, which is O(kn) , where k is a constant that limits the size of your data relative to your input size using O(n^k) . Although this view is usually performed with integers, a small modification allows you to use it for doubles, as described in this stackoverflow article:

Radix Doubling Sort