I was looking at the possible implementation of stable partition in c : https://en.cppreference.com/w/cpp/algorithm/ranges/stable_partition

it’s stated this is at worst O nlgn.

How is this possible? it seems like in the worst case a rotate is called at every index, resulting in an O n**2 algorithm.

CodePudding user response：

As ALX23z notes, the sample implementation is not conforming with respect to running time. Here is what an O(n log n) in-place stable_partition could look like (at least from an algorithms perspective; if you want a library-grade implementation go look at the actual libraries).

#include <algorithm>

template <typename Iterator, typename Predicate>
Iterator my_stable_partition(Iterator first, Iterator last,
                             Predicate predicate) {
  auto n = std::distance(first, last);
  if (n <= 1) {
    if (n == 1 && predicate(*first))
        first;
    return first;
  }
  auto middle = first;
  std::advance(middle, n / 2);
  auto a = my_stable_partition(first, middle, predicate);
  auto b = my_stable_partition(middle, last, predicate);
  return std::rotate(a, middle, b);
}

Here's a quick and dirty test.

#include "my_stable_partition.cc"
#include <assert.h>
#include <stdlib.h>
#include <vector>

bool odd(int n) { return n % 2 == 0; }

int main() {
  for (int i = 0; i < 1000; i  ) {
    std::vector<int> arr(i);
    long long checksum = 0;
    for (int &x : arr) {
      checksum  = x = random() / 31337;
    }
    auto mid = my_stable_partition(arr.begin(), arr.end(), odd);
    for (auto it = arr.begin(); it != mid;   it) {
      assert(odd(*it));
      checksum -= *it;
    }
    for (auto it = mid; it != arr.end();   it) {
      assert(!odd(*it));
      checksum -= *it;
    }
    assert(checksum == 0);
  }
}