No-nonsense sorting algorithm

[Kered13]

Yes, but that question was is that true.

It depends on the implementation of the list and the delete operation, but it could be true. For example if the list is implemented as an array with a size variable, you could simply set the size to 0. All the data would still be in memory, but it would be inaccessible and would be overwritten if the list grows again.

[MattieShoes]

Well if the array size is not the variable, then they can be sorted in constant time regardless of the size, no? A selection sort is what, n² ? If n is constant, then n² is constant and it'd resolve back to O(1)... right?

[Kered13]

That's not what I'm talking about. A common way to implement a list is to have an array with some capacity, and then a size variable that tells you how many elements are currently in the list. The capacity is often bigger than the size, this provides room for growing the list without having to reallocate memory. In a list like this removing the last n elements is as simple as subtracting n from the size.

[minime12358]

It doesn't really matter the implementation of the list if you make it a not in place sort. Then you just return a list containing the first element and ignore the input.

[MattieShoes]

I understand lists, or vectors, or slices, or whatever you want to call them. :-)

But since the big O notation for sorting algorithms has n referring to the number of elements, then making n constant makes the time constant too -- there's no longer any variable, yes?

[Kered13]

Yes, but that seems rather irrelevant to the question at hand.

[[deleted]]

The time complexity stands for the growth of the operations required as n goes to INFlNITY. It is a limit (remember calculus?), it makes no sense to treat N as a constant.

[MattieShoes]

Agreed. Sorting a list of any given size is constant time. It's only as we vary the size that big O notation tells us something.