[dspillett]

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.