Is there anyway to optimize sort on this kind of data?

Question

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:

1. 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

2. 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

3. 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

4. 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 of swapping around and ruins (ie reverse) sorted subsequences so there should be some way to improve on it by exploiting structure of the data, unfortunately all my tries fail so far.
If you are curious what kind of data is that, those are sets of poker hand evaluated on various boards already sorted on previous board (this is where sorted subsequences come from).

The function is in C. I use Visual Studio 2010. Any ideas ?

Sample data: http://pastebin.com/kKUdnU3N
Sample full execution (1176 sorts): https://dl.dropbox.com/u/86311885/out.zip

Answer 1

What if you first do a pass through the array to group the numbers to get rid of duplicates. Each number could go into a hashtable where the number is the key, and the number of times it appears is the value. So if the number 750 000 appears 57 times in the array, the hashtable would hold key=750000; value=57. Then you can sort the much smaller hashtable by keys, which should be less than 100 elements long.

With this you only need to make one pass through the array, and another pass through the much smaller hashtable key list. This should avoid most of the swaps and comparisons.

Answer 2

You can check out this animation, which I saw from this post

I think your problem falls into the "few unique" category, where 3-way partition quick sort and shell sort are very fast.

update:

I implemented some sorting algorithms based on the pseudo codes on sorting-algorithms.com and run them on the sample data given by OP. Just for fun:

insertion 0.154s

shell 0.031s

quick sort 0.018s

radix 0.017s

3-way quick sort 0.013s

Answer 3

Seems like a Radix Sort or a Bucket sort would be the way to go since they can be efficient on integers.

Radix sort's efficiency is O(k·n) for n keys which have k or fewer digits. Sometimes k is presented as a constant, which would make radix sort better (for sufficiently large n) than the best comparison-based sorting algorithms, which are all O(n·log(n)). While bucket sort is O(N*k) for n keys and k buckets.

It may come down to the constant (K) factor for radix sort. From my Java experimentation. Also, it's worth noting that radix doesn't fair so well with sorted elements.

100k integers:

Algorithm           Random  Sorted  Reverse Sorted
Merge sort          0.075   0.025   0.025
Quicksort           0.027   0.014   0.015
Heap sort           0.056   0.03    0.03
Counting sort       0.022   0.002   0.004
Radix sort          0.047   0.018   0.016

500k integers:

Algorithm           Random  Sorted  Reverse Sorted
Merge sort          0.286   0.099   0.084
Quicksort           0.151   0.051   0.057
Heap sort           0.277   0.134   0.098
Counting sort       0.046   0.012   0.01
Radix sort          0.152   0.088   0.079

1M integers:

Algorithm           Random  Sorted  Reverse Sorted
Merge sort          0.623   0.18    0.165
Quicksort           0.272   0.085   0.084
Heap sort           0.662   0.286   0.207
Counting sort       0.066   0.022   0.016
Radix sort          0.241   0.2     0.164

10M integers:

Algorithm           Random  Sorted  Reverse Sorted
Merge sort          7.086   2.133   1.946
Quicksort           4.148   0.88    0.895
Heap sort           11.396  3.283   2.503
Counting sort       0.638   0.181   0.129
Radix sort          2.856   2.909   3.901

It seems like 500k items is when the constant starts favoring radix sort over quicksort.

Answer 4

There is an algorithm that takes advantage of sorted sub-sequences. It is a variant of Merge Sort called Natural Merge Sort. I can't find a good example of an implementation in C, but it doesn't look too hard to implement from scratch. Basically it goes something like this:

1. You need a struct containing two ints, the index and length of a sub-sequence. Create a new array (or probably a linked list) of these structs.
2. Iterate through your entire array once and every time a value is smaller than the previous value it is the start of a new sub-sequence so create a new struct and assign the position of the sub-sequence, and assign the length of the previous sub-sequence to the previous struct.
3. Iterate through your structs and perform the merge operation on them in pairs.
4. Repeat step 3 until all are merged.

The merge operation is the same as the merge operation in Merge Sort. You have a pointer to the start of each sub-sequence. Whichever is smaller should be at the start of the sub-sequence, so move it there if it isn't already and advance the pointer on the sub-sequence you moved it from. Continue merging the two sub-sequences until they are fully sorted.

You may be able to combine this with Oleski's answer to create a sort of linked list where each node contains a value and the number of times a value occurs in a row within a subsequence. Then when you are merging, if you encounter equivalent values you add their cardinalities together to merge several identical values at once with a single addition. You would not need to make a hash for this potential optimization.

Answer 5

Build a hash table and allocate an array. For each item in the input array, check to see whether that item is in the hash table. If yes, then increment its value. If not, insert it into the hash table with value 1 and append it to your array.

Sort the array. For each item in the array, write that item into the output a number of times equal to its count in the hash table. Fin.

EDIT: You can clear and re-use the hash table for each array you need to sort.

Answer 6

I would try a hand-coded qsort with the special trick that at each node you store the number, and the count of times it occurs. When you see it again, you increment the count.

Always take the pivot from the middle of the array so that sorted subsequences don't give you a series of bad pivots.

Answer 7

Given the sorted runs, one reasonable possibility would be to use an in-place merge to put those runs together into large sorted runs until your entire array is sorted. Note that if the function just needs a C interface (rather than having to be written in C itself), you could use the std::inplace_merge from the C++ standard library, but write your function with extern "C" linkage specification, so you can use it from C.

Answer 8

GNU's qsort is frankly very good and dificult to beat, but I've recently converted most my qsort calls to calls to tim_sort by Christopher Swenson, which can be found at https://github.com/swenson/sort/blob/master/sort.h - it's really extremely good. Btw, it explicitly exploits already sorted segmens, like the ones in your data.

I'm doing C++, and have "templatized" Christopher's (pure C macros) code, but it probably doesn't change the fact that it's hands down an absolute winner on your data. The following, in GNU-64 with -O3, is without appeal I believe:

Sort test:

• qsort: 00:00:25.4

• tim_sort: 00:00:08.2

• std::sort: 00:00:15.2

(that's running each of the sorts a million times).