4 ms·

What's the asymptotical complexity of running around and fixing things?

• dspillett 8y ago
  That stage is presumably a more traditional sort operation. If the first stage does a good job of estimating the correct order this could also be O(n) or as close to as makes no odds. If the set isn't modelled properly by the earlier stages it will still be O(n log n). Obviously that operation needs to be an algorithm that can take advantage of partially pre-sorted input.