The current implementation has quadratic time complexity rather than O(n log n) time complexity. This is a known issue with boost: see https://svn.boost.org/trac10/ticket/13140. The problem is that the constructor inserts each input element by using a binary search, but the insertion into the middle of the backing vector has to shift elements over to make room.

 The known performance impact on the MongoDB server code base is being fixed separately under SERVER-35693. However, we may also wish to patch our vendorized version of boost in order to avoid future issues of this nature.