Identify MSVC's single-pivot partitioning algorithm

101 Views Asked by At

I'm looking at how MSVC implements std::sort, and I can't figure out the partitioning method used. Here's what I know from the code:

  1. It's a variant of introsort, which falls back to insertion sort if the section size is _ISORT_MAX or below, and does heapsort if recursive depth reaches 1.5log(N)
  2. The pivot selection uses Sedgewick's median-of-3 method from the first, mid, and last element. But if the input is larger than 40, it uses Tukey's ninther instead (take 3 median-of-3s, and get median from them).

However, after getting the pivot, I don't really understand what's being done to partition the container. It's not the popular Hoare's, Lomuto's, or Bentley-McIlroy's partition method that I've seen. This is the point where the partitioning starts: https://github.com/microsoft/STL/blob/master/stl/inc/algorithm#L7474

If you know what is this partitioning method, please do refer me to any links, paper, etc. A name would be useful too.

Thanks.

0

There are 0 best solutions below