Efficace ordinamento funzionale

Question

Sto programmando una funzione per un TI-Nspire , così posso 't utilizzare i comandi incorporati dall'interno di una funzione. Qual è l'algoritmo più generalmente efficienti per l'ordinamento di un elenco di numeri senza modificare la lista stessa? (Ricorsione e la lista-splitting sono gioco equo, come è uso generale della matematica.)

Answer 1

Mergesort è semplice, semplice, efficiente e stabile:. Dividere la lista, ordinare in modo ricorsivo, e unire i risultati

Per essere più specifici, mergesort prende O (N log N), che è asintoticamente ottimale. Inoltre, in pratica (con entrambi gli algoritmi modificati per liste brevi sottoliste con un fine particolare ordinamento), per fusione può essere un concorrente vicino alla Modified quicksort utilizzati nei / C ++ librerie standard C.

Edit. Differenza sul posto come tipi quicksort e inserzione, mergesort richiede memoria ausiliaria, ed è semplice da implementare copiando anziché scambiando

Answer 2

timsort viene utilizzato in pitone e Java SE 7. prende il meglio di merge sort e inserzione. Insertion sort è O (n ^ 2), ma con piccole liste di numeri è più veloce di merge sort!

Così si può utilizzare questo come un algoritmo di ordinamento generica come dichiarato qui