[boost] Fwd: [sort][container] Challenge for sorting experts, an improved stable sort

Subject: [boost] Fwd: [sort][container] Challenge for sorting experts, an improved stable sort
From: Francisco José Tapia (fjtapia_at_[hidden])
Date: 2015-09-22 00:58:31

Hi Jon,

If the elements in the flat associative container are sorted, you need only
to sort the elements to insert and after do a fusion of the two parts.

If your container admit repeated elements, you can use the std::sort, if
not, you must use an stable sort , and delete the repeated.

You have several algorithms for to do a stable sort. In the library we are
developing (https://github.com/fjtapia/sort_parallel ) you have a
smart_merge_sort, which is a very fast stable sort and use only one half of
the memory used by the data, is exception safe and use the move semantics

I didn't see any implementation of the stable sort algorithms without
additional memory, in any library GCC, TBB, IPP … I suppose because they
are slow.

If you have 100 elements and want to insert 30 elements, need to resize the
vector to 130 elements, the last 30 are empty.

If you have other vector with the data to insert, you can use
smart_merge_sort, and use as auxiliary memory the last 15 elements of the
main vector. After sort, delete the repeated elements. And with the two
vectors you must do a half_merge fusion , and all is done.

With this method you need only the vector for to sort the elements to
insert.

If you want I can write a small program doing this, using the code of the
library.