Originariamente inviato da satifal
In effetti se occorre ordinare prima l'array la complessità totale dell'algoritmo non può essere lineare in quanto la complessità degli algoritmi di ordinamento più semplici è O(n^2) mentre il mergesort o il quicksort hanno complessità O(n log n).
Tanto per passare per quello puntiglioso

quicksort ha complessità media O(n log(n)) ma ha complessità O(n^2) nel caso pessimo
mentre il margesort ha complessità O(n log(n))