I am sorting array of integers keys.
Information about the data:
- Arrays are 1176 elements long
- Keys are between 750 000 and 135 000 000; also 0 is possible
- There are a lot of duplicates, in every array there are only between 48 and 100 different keys but it's impossible to predict which values out of whole range those will be
- There are a lot of long sorted subsequences, most arrays consists of anywhere between 33 and 80 sorted subsequences
- The smallest element is 0; number of 0's is predictable and in very narrow range, about 150 per array
What I tried so far:
stdlib.h qsort;
this is slow, right now my function spends 0.6s on sorting per execution, with stdlib.h qsort it's 1.0s; this has the same performance as std::sort
Timsort;
I tried this: https://github.com/swenson/sort and this: http://code.google.com/p/timsort/source/browse/trunk/timSort.c?spec=svn17&r=17; both were significantly slower than stdlib qsort
-
their combination of quick sort and insert sort is the fastest for my data so far; I experimented with various settings and pivot as middle element (not median of 3) and insert sort starting with 28 element sub arrays (not 8 as default) gives the best performance
shell sort;
simple implementation with gaps from this article: http://en.wikipedia.org/wiki/Shellsort; it was decent, although slower than stdlib qsort
My thoughts are that qsort does a lot o