3 ms·
How do you do an in-place merge in linear time (i.e. without blowing up the time complexity)? I've been chasing that for many years with no solution. https://ww
by nayuki 3y ago
How do you do an in-place merge in linear time (i.e. without blowing up the time complexity)? I've been chasing that for many years with no solution. https://www.nayuki.io/page/is-there-an-ideal-comparison-sort https://www.nayuki.io/page/is-there-an-ideal-comparison-sort
- colanderman 3y agoOh, I don't know that there's a way to do that. The G++ implementation uses free memory if available for linear merge, else it falls back to n log n merge. I don't think this affects the performance of insert though (which is already log n due to the necessary lookup).