Re: What's the time complexity of sorting a list using list.sort()
I thought the O(n) space overhead for merge sort was when operating
on arrays. For linked list it is a constant amount.
If I recall correctly, the STL that shipped with VC++6 used 16 "empty"
linked lists, but Dinkumware suggested increasing to 32.
Re: What's the time complexity of sorting a list using list.sort()
Quote:
Originally Posted by
laserlight
By O(n) space overhead, I think that you are talking about the fact that a linked list would need at least a pointer for each node, in addition to the actual data stored.
Yes, that's what I was referring to.
Quote:
Originally Posted by
laserlight
However, this space overhead could be relatively small, depending on the size of each individual node's data, whereas the space overhead of an extra vector would be relatively large. Granted, we could sort a vector of pointers to elements of the vector instead, but that would not be sorting the original vector.
Ok, I get it now. I was thinking that merge sort on a vector could just keep pointers to the original data and sort them. But then indeed the original data still wouldn't be sorted.
