Qual è il modo più efficiente per ordinare un milione di interi a 32 bit?

• Dipende da cosa intendi per efficiente. Tempo di esecuzione? uso della memoria? tempo al primo risultato (algoritmo online)? tempo del programmatore? Quanto spesso lo farete? Ti interessa il tempo trascorso (di clock) o il tempo della CPU - cioè, dovresti usare tutti i core disponibili, o stanno già facendo altro lavoro utile?
• Stai confrontando il tempo medio? il tempo del caso peggiore?
• Dipende da cosa sai della distribuzione (come menzionato da Joe Zbiciak). La maggior parte delle risposte assume una distribuzione uniforme, che non si incontra molto spesso nelle applicazioni reali. Quanto è probabile che l'input invochi il comportamento del caso peggiore?
• Dipende da dove provengono gli interi - sono tutti nella RAM, provengono da una connessione di rete lenta, sono sparsi in un sistema distribuito?
• Dipende da dove vanno gli interi - vengono richiesti uno per uno da un utente umano? Avrete effettivamente bisogno di ordinarli tutti? Il risultato dovrà essere distribuito?
• Un risultato approssimativo è abbastanza buono per i vostri scopi? Una risposta quasi corretta in 1ms sarebbe meglio di una risposta esatta in 30ms?
• Quanta RAM avete a disposizione per lo spazio di lavoro?
• Perché li state ordinando in primo luogo?
• Quali altri casi dovrete considerare in futuro? Quanto è probabile che il caso d'uso cambi a 64-bit interi, diciamo? Quanto è probabile che abbiate bisogno di portare il codice su altri processori o architetture? Questa è destinata ad essere una libreria di uso generale o è dedicata a qualche problema specifico importante? Avrete bisogno di ordinare 100 milioni di numeri interi? Avrete mai bisogno di ordinare più numeri di quanto abbiate spazio di indirizzamento (non è probabile al giorno d'oggi, dato che la maggior parte delle macchine sono a 64 bit... ma ci sono ancora alcune applicazioni che girano su microcontrollori a 32 bit) o RAM?

Per esempio:

• Se il vostro input è quasi ordinato all'inizio, l'ordinamento a inserimento può essere la soluzione migliore, anche se è O(n^2) in generale. E non ha bisogno di memoria ausiliaria.
• Se ci sono solo 1000 valori distinti, allora un algoritmo di conteggio sarà il migliore.
• Se i vostri interi arrivano in serie, un algoritmo heap potrebbe essere il migliore. Se sono distribuiti, potreste volere un algoritmo distribuito (anche se l'overhead per qualcosa di piccolo come 1m elementi probabilmente non lo rende utile).
• Se il tempo al primo risultato è critico, un selection sort è la scelta migliore.
• Se state ordinando per rendere più facile la ricerca, una tabella hash è solitamente migliore. If you’re sorting them to find the median, there are more efficient algorithms.

etc.

But… most of the time, for such a small problem, you can ignore all the subtleties and just call the system sort algorithm.