Structura problemei cere implementarea unui 'algoritm de sortare pe baza de comparatii':http://en.wikipedia.org/wiki/Comparison_sort. Exista, de asemenea, algoritmi de sortare care nu compara explicit elementele si care au performante mai bune pentru anumite cazuri particulare ale structurii datelor de intrare; acestia nu se preteaza insa cerintelor impuse in cazul de fata.

Orice algoritm de sortare bazat pe comparatii trebuie sa efectueze, pentru a putea distinge corect toate cele <tex>N!</tex> permutari posibile ale sirului de valori, <tex>\Omega \left( N \cdot \log N \right)</tex> comparatii (o justificare a acestui rezultat se afla 'aici':http://www.cs.utexas.edu/~vlr/s07.357/notes/lb-apr5.pdf). Din aceasta perspectiva, algoritmi precum 'Merge Sort':http://en.wikipedia.org/wiki/Merge_sort, 'Heapsort':http://en.wikipedia.org/wiki/Heapsort sau 'Introsort':http://en.wikipedia.org/wiki/Introsort sunt optimi, executand <tex>\Theta \left( N \cdot \log N \right)</tex> operatii in cazul cel mai defavorabil. Dintre acestia, Merge Sort foloseste <tex>\mathit{O}\left( N \right)</tex> memorie suplimentara in implementarea clasica, deci nu se va incadra in restrictiile problemei.

Orice algoritm de sortare bazat pe comparatii trebuie sa efectueze, pentru a putea distinge corect toate cele <tex>N!</tex> permutari posibile ale sirului de valori, <tex>\Omega \left( N \cdot \log N \right)</tex> comparatii (o justificare a acestui rezultat se afla 'aici':http://www.cs.utexas.edu/~vlr/s07.357/notes/lb-apr5.pdf). Din aceasta perspectiva, algoritmi precum 'Merge Sort':http://en.wikipedia.org/wiki/Merge_sort, 'Heapsort':http://en.wikipedia.org/wiki/Heapsort sau 'Introsort':http://en.wikipedia.org/wiki/Introsort sunt optimi, executand <tex>\Theta \left( N \cdot \log N \right)</tex> operatii in cazul cel mai defavorabil. Dintre acestia, Merge Sort foloseste <tex>\mathit{O}\left( N \right)</tex> memorie suplimentara in implementarea clasica.

Un alt algoritm de sortare foarte popular este 'Quicksort':http://en.wikipedia.org/wiki/Quicksort. Desi complexitatea sa pentru cazul cel mai defavorabil este <tex>\mathit{O}\left( N^2 \right)</tex>, in practica se comporta foarte bine si cunoaste multe imbunatatiri (detalii in prezentarea profesorului Robert Sedgewick 'aici':http://www.sorting-algorithms.com/static/QuicksortIsOptimal.pdf si a profesorului Jon Bentley 'aici':blog/three-beautiful-quicksorts).