Hi all,
I'm now reading the source code of the rtree implementation in boost::geometry, especially in
pack_create.hpp, I found that std::partial_sort is used to find the median along the longest dimension, which is then used to split the array and perform the splitting recursively:
// pack_create.hpp, around line 281
partial_sort(first, median, last, ...);
per_level_packets(first, median, ...);
per_level_packets(median, last, ...);
It seems to me that the sortedness of the first half is never used, in this case, I guess that std::partial_sort may be replaced by std::nth_element, which should be faster.