Geometry Boost List: [geometry] partial_sort vs nth_element in the rtree implementation

Subject: [geometry] partial_sort vs nth_element in the rtree implementation
From: Lu Wang (coolwanglu_at_[hidden])
Date: 2014-02-28 06:36:41

Hi all,

   I'm now reading the source code of the rtree implementation in
boost::geometry, especially in
pack_create.hpp<http://svn.boost.org/svn/boost/trunk/boost/geometry/index/detail/rtree/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.

  Is there any particular reason that partial_sort is used?

  Thanks!

  regards,
  - Lu