How is stable_partition an adaptive algorithm?
algorithm, c++, quicksort, stl
Solution
It depends on how much memory is available.
If you have enough memory, one way is to simply create a big enough buffer, insert the respective elements from the front and back and put it back into the original when done. This will take O(n) time.
If there isn't enough memory, this page mentions a O(n log n) in-place approach (there might be another approach as well) - if you want to rearrange `-` to the front and `+` to the back, you repeatedly find subarrays in the form `++++---` and rearrange it (stably) to `---++++` (which can be done with 3 reverses - reverse the whole subarray, then the negative part, then the positive part).
The physical checking for enough memory can simply be done by trying to allocate the memory and checking for failure. One way to do this is with a `new`, which can either throw an `std::bad_alloc` or return a null pointer, depending on the version used, if it fails to allocate the memory.
Problem
stable_partition is a function template present in algorithm header file of c++ STL. I read that it is an adaptive algorithm and its time complexity is O(n*logn) or O(n) depending on some factors.Can someone explain me what are those factors and how the time complexity depends on those factors. Thank You !