None. It depends on the circumstances.

Naturally, the next question is: Which one must be used in each case?

The best choice is almost always the implementation that comes with the language you are using.

In some cases you can choose among the following options:

1. Stable sort. Generally requires O(N) additional memory, that is, an amount proportional to the data being sorted.
2. Non-stable sort. Requires very little additional memory, but does not respect the previous order of the elements considered equal to each other.

More details in: stable sort
and in: “big O” notation.

In C++, for instance, you can choose between std::sort and std::stable_sort.

In the field of sorting with little additional memory there have been several favorites along the history: ShellSort (1959), quicksort (1960), heapsort (1964) and more recently introsort (1997), which is a hybrid of quicksort, heapsort and insertion sort.

Mergesort (1945) dominated many years in the field of stable sorting. Its replacement seems to be Timsort (2002). It is also a hybrid, this time of mergesort, insertion sort and a few more tricks.

I will discuss the few cases where it makes sense (in my opinion) to tailor your own implementation of a sorting algorithm. But I’ll do it later ;-)

ProjectEuler.net is a great invention that I discovered a couple of years ago. It houses a very interesting collection of programming problems.

The first ones are relatively simple. Then the difficulty increases as you advance through the list of problems.

Every problem is designed to be solved with less than one minute of processing in a normal computer. Many take just a few microseconds. Any language like C or Java with 64 bit integers should suffice. Many people use other languages.

In principle, new users only have access to the problem statements.

For every problem there is a forum where previous users have been sharing their solutions. For many problems there is also a PDF overview explaining possible solutions.

But users can only access the forum and the PDF overview of a problem after solving it and entering the correct answer on the website.

At first glance this might seem a nonsense. What’s the point if the user has already found the solution? There’s a big point, indeed! There are often several ways to solve a problem and they are not all equally efficient. The forum and the PDF overview contain vital clues to approach future problems.

Out of the hundreds of problems that exist in Project Euler, I have solved 81 to date. As a result I have learned a lot about combinatorics and dynamic programming, among other things. About the latter, by the way, I plan to write some day on this blog.

Aside from having solved a few problems, I can proudly say that I contributed my bit to Project Euler: I volunteered for the preparation of the PDF overviews for problems 31 and 53.

Unfortunately, Project Euler has been a while running at half speed. Administrators discovered that someone had sneaked into their database and they shut down the website. They reopened it later but with “reduced functionality”. That is, you can access the problem statements and you can check whether a solution is correct, but there are no forums or PDF overviews.

Reproducing here the problem statements or giving clues to the solutions would go against the philosophy of Project Euler, so I will just link the statements …

Problem 31: coin sums

Problem 53: combinatoric selections

… and provide the PDFs with the same requirement as prescribed in Project Euler, i.e., having solved the problems previously:

[..]

Update (17th of August, 2014): Project Euler is working again, so I have removed the PDFs from this blog.