Where can I find several significant sorting algorithms tests cases?

Question

I want to develop a very efficient sorting algorithm based on some ideas that I have. The problem is that I want to test my algorithm's efficiency against the majority highly appreciated sorting algorithms that already exist.

Ideally I would like to find:

• a large bunch of sorting tests that are SIGNIFICANT for providing me with the efficiency of my algorithm
• a large set of already existing and strongly-optimized sorting algorithms (with their code - no matter the language)
• even better, software that provides adequate environment for sorting algorithms developers

Here's a post that I found earlier which contains 2 tables with comparisons between timsort, quicksort, dual-pivot quicksort and java 6 sort: http://blog.quibb.org/2009/10/sorting-algorithm-shootout/ I can see in those tables that those TXT files (starting from 1245.repeat.1000.txt on to sequential.10000000.txt) contain the test cases for those algorithms, but I can't find the original TXT's anywhere!

Can anyone point me to any link with many sorting test-cases AND/OR many HIGHLY EFFICIENT sorting algorithms? (it's the test cases I am interested in the most, sorting algorithms are all over the internet)

Thank you very much in advance!

Answer 1

A few things:

• Quicksort goes nuts on forward- and reverse sorted lists so it will need other list types.
• Testing on random data is fine, but if you want to compare the performance of different algorithms that means you cannot generate new random data every time or your results won't be reliable. I think you should try to come up with a pseudo"random" algorithm that writes data in in an order that is based on the number of entries. That way the data generated for lists of size n, 10n and 100n will be similar.
• Testing of sorting is not primarily about speed (until an algorithm has been finalized) but the ratio of comparisons to entries. If one sort requires 15 comparisons per entry in a list and another 12 for the same list the second will be more efficient even if it executed in twice the time. For the more trivial sorting concepts the number of exchanges necessary will also come into play.
• For testing use a vector of integers in RAM. If the algorithm works well the vector of integers can be translated to a vector of indeces into a buffer containing data to be compared. Such an algorithm would sort the vector of indeces based on the data they point to.