Originariamente inviato da LeaderGL
Mi spiace ma se non sbaglio è matematicamente dimostrato che il limite è O(nlog n).
No. Quel limite è matematicamente dimostrato per gli algoritmi di ordinamento a confronto, classe a cui questo non appartiene.

Comunque, per capire che elementi vengono dall'array di partenza e quali invece non sono stati toccati puoi o usare un array separato di bool per segnarti quali valori sono stati effettivamente scritti, oppure scegliere un valore particolare (ad esempio INT_MAX) a cui inizializzare l'array di destinazione, in modo da poter individuare subito gli elementi che non sono stati toccati.