3 ms·
A tradeoff to be aware of: the introduction of sort raises the complexity of the solution from O(n) to O(nlogn).
by praptak 16y ago
A tradeoff to be aware of: the introduction of sort raises the complexity of the solution from O(n) to O(nlogn).
- aphyr 16y agoI saw that and flipped out. It also requires an extra two scans through the list, in addition to the memory overhead for the temporary structures. Happily, the merge-with suggestion is much more efficient.
- amalcon 16y agoThe enormous irony here is that this is one of the rare cases that you could actually speed up using a non-comparison sort, like a counting-sort... except that this defies the point, because the first half of counting-sort is solving the problem we originally set out to solve.