What's the memory complexity of std::sort? I assume O(n), but I can't find any ref for it!
Also, do I understand the term memory complexity correctly? I understand it as how much memory the algorithm will need to run. So, for example, if std::sort implements an in-place sort, it will take O(n).
Code - functions and small libraries I use
It’s 2014 and I still use printf() for debugging.
"Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson
Looking at the standard I found this:
Jim
O_oWhat's the memory complexity of std::sort? I assume O(n), but I can't find any ref for it!
Quality of implementation issue. Different implementations use memory more effectively than other implementations. Beyond that, the standard allows specializations for `std::sort' for different iterators categories allowing the implementation to choose between a few different options so long as the complexity (time) matches the requirements.
The general implementation is a hybrid burning stack memory from a variation of Quicksort before becoming InsertionSort or similar.
You do not appear to understand.Also, do I understand the term memory complexity correctly? I understand it as how much memory the algorithm will need to run. So, for example, if std::sort implements an in-place sort, it will take O(n).
The measurement of memory complexity is how many extra slots--each slot as in sizeof(element)--required to perform the operation. The memory use by the collection isn't counted.
Thus a pure "in-place" algorithm has O(1) memory complexity, but that notation just implies a constant. The actual implementation may use more slots, but the number of slots used remains unrelated to the number of elements.
With a O(n) memory complexity algorithm, the algorithm requires a number of extra slots equal to the number of elements.
Soma
“Salem Was Wrong!” -- Pedant Necromancer
“Four isn't random!” -- Gibbering Mouther
O_o
@jimblumberg:
Good on you for looking in the standard, but you are looking at one of the member functions of one of the containers.
Different containers have somewhat different options and requirements for the member function version because the implementation knows more about the characteristics of the implementation than the generic `std::sort' free function may ever know just from inspection the iterator categories.
Soma
“Salem Was Wrong!” -- Pedant Necromancer
“Four isn't random!” -- Gibbering Mouther
Okay what about section 24.4.1, this appears to be the "free" std::sort(), the complexity here is similar to the above.
Jim
Thanks Soma! Jim, isn't that the time complexity? I am interested in the memory complexity!
Code - functions and small libraries I use
It’s 2014 and I still use printf() for debugging.
"Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson
^_^Thanks Soma!
Yep.
@jimblumberg:Okay what about section 24.4.1, this appears to be the "free" std::sort(), the complexity here is similar to the above.
The time complexity is similar. I didn't call your attention to the section because the time complexity was different.
The other stuff is not necessarily similar. For example, the `std::list::sort' member function is a stable sort while the free `std::sort' is not.
Soma
“Salem Was Wrong!” -- Pedant Necromancer
“Four isn't random!” -- Gibbering Mouther
The point is: the standard appears to offers no guarantees about the memory complexity (as can be seen from the snippets quoted from the standard), so ask your standards library provider!Originally Posted by std10093
The memory overhead for most implementations of std::sort would be related to the depth of recursion and the number of local variables stored onto the stack for each level of recursion. The HP / Microsoft STL implementation of std::sort uses quick sort until/unless it detects that the recursion level is getting too deep in which case it switches to heap sort. If the size is small, such as 32 or less, then it uses insertion sort.
The complexity given is not even time, but numbers of comparisons.
@rcgldr, I would agree.
Code - functions and small libraries I use
It’s 2014 and I still use printf() for debugging.
"Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson
That is a form of time complexity. It is evident that std::sort is expected to be implemented by a general purpose comparison based sorting algorithm, so number of comparisons seems to be a reasonable measure for counting.
Look up a C++ Reference and learn How To Ask Questions The Smart Way
