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

Question

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

I don't like quick sort, merge sort because they are harder to implement than bubble sort, selection sort, insertion sort..

Just wondering what is the best (simple to implement and with some best cases complexity less than O(N²) if many numbers are already sorted) simplest sorting algorithm in this case

The numbers to sort are type of doubles.

Answer 1

I once compared some sorting algorithms. I found comb sort and heap sort 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 multiple algorithms on your data set and choose the best one for your need.

EDIT Adding calculation of magic number I used for comb sort. I found this in some book (that I don't remember any more) years ago.

Answer 2

You could use radix sort, Which is O(kn) where k is a constant bounding the size of your data with respect to your input size in an O(n^k) manner. Although this sort is usually done with integers, a slight modification allows it to be used for doubles, as mentioned in this stackoverflow post:

Radix sort for doubles