2 ms·

Are you talking about this? https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_algo.h#L2491 https://github.com/gcc-mirror/gcc/blob

Are you talking about this? https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_algo.h#L2491 https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-... Do you know what the time complexity of their merging algorithm is? As a side note, an optimal merging algorithm is in the paper called "On Optimal and Efficient in Place Merging", and it's too complicated for me to expect it in a standard library implementation. (Although the STL doesn't need to be optimal, I think the sub-optimal linear-time algorithms are also complicated enough to not be used for the standard library, but correct me if I'm wrong.)

CJefferson 12y ago
I know the complexity of stable_sort (which uses this) is O(n. log n) with extra memory (which is fairly obvious extra buffer), and the intention is that without extra memory the sort is O(n.log^2 n). I assume that algorithm meets that target, but I'll admit I'm not positive it does.
- wfunction 12y ago
  See, that would violate the standard. The standard mandates O(n log n), but I don't think any implementation follows this. (Again, that complexity is indeed possible, but quite challenging and not something I've seen in standard library implementations.)
  - CJefferson 12y ago
    No, my previous message was a quote from the standard. O(n log^2 n) is fine when no extra memory is available. As you say, this could in principle now be tightened. In the past the standard used to allow O(n^2) std::sort to permit naive quicksort implementations, which has now been tightened to O(n log n). Here's the relevant quote from stable_sort: > Complexity: It does at most N log^2(N) (where N == last - first) comparisons; if enough extra memory is available, it is N log(N).
    - wfunction 12y ago
      Ohh sorry, I thought you were talking about the merge, not the sort. Yes O(n log n) is allowed for the merge, but what I'm saying is that the Dr. Dobbs article's in-place merge sort is actually not quite an in-place variant of merge sort: its complexity (as far as I can tell) is O(n log^2 n) rather than O(n log n).

CJefferson 12y ago

I know the complexity of stable_sort (which uses this) is O(n. log n) with extra memory (which is fairly obvious extra buffer), and the intention is that without extra memory the sort is O(n.log^2 n). I assume that algorithm meets that target, but I'll admit I'm not positive it does.

wfunction 12y ago
See, that would violate the standard. The standard mandates O(n log n), but I don't think any implementation follows this. (Again, that complexity is indeed possible, but quite challenging and not something I've seen in standard library implementations.)
- CJefferson 12y ago
  No, my previous message was a quote from the standard. O(n log^2 n) is fine when no extra memory is available. As you say, this could in principle now be tightened. In the past the standard used to allow O(n^2) std::sort to permit naive quicksort implementations, which has now been tightened to O(n log n). Here's the relevant quote from stable_sort: > Complexity: It does at most N log^2(N) (where N == last - first) comparisons; if enough extra memory is available, it is N log(N).
  - wfunction 12y ago
    Ohh sorry, I thought you were talking about the merge, not the sort. Yes O(n log n) is allowed for the merge, but what I'm saying is that the Dr. Dobbs article's in-place merge sort is actually not quite an in-place variant of merge sort: its complexity (as far as I can tell) is O(n log^2 n) rather than O(n log n).