First of all, there are different methods of measuring the quality of sorting algorithms. The two most common ones are time efficiency and space efficiency.
The time efficiency of sorting algorithms depends on the type of language you're using and what is supported - for example,
merge sort is great in many languages, but if you don't have arrays but only lists it will be extremely inefficient. In languages with arrays, such as Java, C, C++, C#, Python, etc. however,
quicksort is the fastest sorting algorithm I can think of off the top of my head.
When it comes to space efficiency, any algorithm that won't use more than the memory needed for exactly those 10^6 numbers is the best you can get.
Mind you, there is a lot of research into sorting algorithms and there may be specialized algorithms for exactly that kind of case. I in your situation would have a look at the
sorting algorithm wikipedia page, especially the part about
comparing algorithms. If you want to look for research, maybe try searching with
Google Scholar, which will search explicitly for research papers.
7
