Originariamente inviato da Andrea1979
...
codice:
// se l'array è ordinato. Altrimenti conviene ordinarlo, per mantenere la complessità
//dell'algoritmo lineare.
...
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).