What about the time taken to do the sorting? Is there some rule of thumb that hints at whether taking the time to sort the data is going to be a net win?
The time it takes to sort an array is a rather well-understood problem. If you can reason about how much performance gain you'll get from looping through a sorted versus unsorted array, you can probably estimate the additional cost of the sort itself.
sorting an array of integers that you know the max value of (like in the question in SO) will take you O(n) with count sort, so this will be pretty damn fast
Comments
What about the time taken to do the sorting? Is there some rule of thumb that hints at whether taking the time to sort the data is going to be a net win?
I would expect sorting to take a lot longer than just summing.
The time it takes to sort an array is a rather well-understood problem. If you can reason about how much performance gain you'll get from looping through a sorted versus unsorted array, you can probably estimate the additional cost of the sort itself.
Unless you have external information, you will need to take at least one pass through the data to determine if its sorted or not.
sorting an array of integers that you know the max value of (like in the question in SO) will take you O(n) with count sort, so this will be pretty damn fast