Francisco,
On Tue Jan 13 2015 at 12:43:00 PM Francisco José Tapia
Hi Steven,
This Christmas I had been working hard. I developed a new version of the merge sort about 10-15% faster than the previous, using an additional memory only ½ of the memory used by the data. The GCC and TBB algorithms use an additional memory as the size of the data.
This version is exception safe. If an exception occurs due to the algorithm ( only throw exceptions in the allocation and deallocation of the additional memory), the integrity of the data is guarantee. You have all the original data (unordered in the allocation, and ordered in the deallocation)
Less memory, comparable speed, and exception safety sounds good.
I examined the TBB version and the secret is the sample sort algorithm. The version of TBB is provisional and it's not exception safe. I am working in the design of a new version of this algorithm exception safe. The actual version of the parallel stable algorithm is about 20% slower than the TBB version in the worse case, but when the size of the elements grows, the indirect version is faster than all the others, with 64 bytes, is around 10% faster than the best TBB version, with 128 bytes , the best version of TBB is around a 90% slower, and with 256 is 240% slower.
Yes, indirect sorting is clearly superior for large data types, and it would be good to make it as easy as possible to use. It'd be nice to also have a simple wrapper that can be use the spreadsort algorithm with indirect sorting too.
I am in the process of integrating the first version of the boost sort library in https://github.com/boostorg/sort. It would be good to integrate your testing with the tests in that library.