Edit Question - KnowledgeHub

Title Body

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 http://www.ucw.cz/libucw/ ; 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

Tags (comma-separated) Cancel