1

The docs from www.cppreference.com says that the complexity of std::stable_sort() is

O(n * log(n)^2) [...]. If additional memory is available, then the complexity is O(n * log(n)).

What algorithm would meet this requirement, and how much is the specified "additional memory"?

Donny Chan
  • 55
  • 7
  • _"What implementation meets this requirement ?"_ Well, any standard compliant implementation. For example, [libstdc++](https://github.com/gcc-mirror/gcc/blob/d9375e490072d1aae73a93949aa158fcd2a27018/libstdc%2B%2B-v3/include/bits/stl_algo.h#L4977), [libc++](https://github.com/llvm-mirror/libcxx/blob/a12cb9d211019d99b5875b6d8034617cbc24c2cc/include/algorithm#L4696). For the size of the additional memory, well, I guess it's up to the implementation to define what it needs. You can take a look at any implementation (for example libstdc++) and see how much do they take and in which case. – Fareanor Oct 21 '21 at 08:58
  • What implementation? Any compliant. I guess that most implementations uses some form of merge sort (or its variants), which requires an additional "array" of size _n_. – Daniel Langr Oct 21 '21 at 08:58
  • 1
    Since any conforming implementation meets that requirement by definition, are you wondering whether there is any implementation that uses additional memory in order to achieve the lower complexity? – molbdnilo Oct 21 '21 at 09:08
  • @molbdnilo I am wondering what kind of algorithm (or forms of mergesort as mentioned above) would have this complexity, and why is it dependent on available memory. – Donny Chan Oct 21 '21 at 09:12
  • Generally it's a merge sort. [`inplace_merge`](https://en.cppreference.com/w/cpp/algorithm/inplace_merge) has a well known linear time + linear space implementation, and also a well known loglinear time + log space implementation, and the standard requires something at least that good – Caleth Oct 21 '21 at 09:17
  • Big-O complexity hides a lot of detail. You can use a O(n^2) algorithm up to a constant size, and above that use an O(n log n) one, and overall that is still O(n log n), because O(K^2) is O(1) for any constant K – Caleth Oct 21 '21 at 09:20
  • @DonnyChan Merge sort has _O(n log(n))_ time complexity if _O(n)_ auxiliary space is available. If not, the complexity gets higher. – Daniel Langr Oct 21 '21 at 09:20
  • @DanielLangr I am aware of merge sort's complexity, but what is the algorithm that is O(n * logn^2) when there is not enough memory? – Donny Chan Oct 21 '21 at 11:05
  • @DonnyChan Try to look for "in-place merge sort". It is even mentioned here: https://en.wikipedia.org/wiki/Merge_sort#Variants. Relevant post: [How to sort in-place using the merge sort algorithm?](https://stackoverflow.com/q/2571049/580083). IIRC, there is simply no generic _in-place stable O(n log(n))_ sorting algorithm. – Daniel Langr Oct 21 '21 at 11:06

1 Answers1

0

According to the commenters on the question and some further reading, the complexity is specified as such because there is no trivial stable in-place O(nlogn) sorting algorithm. With some further inspection on the source code, the implementation of libc++ and libstdc++ are similar, both are a merge sort where the in-place merge has complexity O(nlogn). As for the "additional memory", the two libraries require N additional memory, where N is the length of the array.

More specifically, instead linearly scanning the two sub-arrays and merging one element at a time, the in-place merge search for a way partition each of the two sub-arrays into two parts (four parts in total), such that when swapping the middle two parts, all elements in the the leftmost two parts are smaller or equal to the rightmost two parts. Then they perform in-place merge on the leftmost and rightmost two part respectively.

Donny Chan
  • 55
  • 7