How to known which algorithm is the best for what situation, when sorting numbers?

Question

Is there some kind of "universal list" of performance of different algorithms in different situations?

I have different databases that save user input (numbers). However some of these sets of numbers are small and some of them are really big (such as the common one). There are negative numbers included.

I remember from when I took algorithms as a course that there are things such as "big-oh notation" and "theta notation", etc. What I am looking for is some way of looking up which algorithm I should use for different un-ordered lists of numbers.

I know that merge sort has the best over all performance with a worst-case time of $n \log n$ however I also know that both insertion sort and quick sort (worst-case $n^2$) sorts better with fewer elements in the given list. There are a few cases of lists being in reverse sort, where can I look up what is the most effective then?

How do I know which of insertion sort or quick sort I should use then?

What is "a small list of numbers that is quicker to sort with quick sort/insertion sort"?

Answer 1

There is a comparison of sorting algorithms on wikipedia which provides most of the information you're looking for, including separate tables for non-comparison based sorts (distribution, radix, etc).

The short answer this question usually gets is "use whatever built-in library you have". This is obviously frustrating because that's a practical answer to an abstract question. It's often phrased as "you shouldn't be worrying about this" yet this is something taught in every introduction to programming and tutorial site, with drastically fewer explanations of what standard library sorting algorithms do. So it shouldn't be surprising that the question is so common. In short, the built-in sorts usually are adaptive, so they use different algorithms depending on the data structure that way you're usually getting the best of all options.

There are lots of websites, animations and videos that visualize sorting algorithms. This tool has 75 different sorts built in as well as different input data like almost-sorted, reversed, duplicates. It's used to make lots of videos. Those can answer a lot of questions quickly just by visualizing the abstract concept of big O.

To answer one of your specific questions, negative numbers should generally be handled with no issue by any sorting algorithm unless its extremely specialized. Most sorts you read about are comparison based so they don't care if you're comparing (-∞ <= 2) or (red <= blue) as long as it can get a valid result out of the comparison.

For the more specific questions you mentioned, I've also wondered about those cases and considered making a big table just as an exercise to cement what I've learned and maybe satisfy someone else's curiosity. However once you start seriously considering publishing something like that you realize it's very difficult to choose a good "reference frame" (what test cases on what hardware) that won't give beginners the wrong idea or get a million corrections from people. It's a somewhat lose/lose scenario so I understand a bit more why people don't do it. (And I'm even more grateful to the people on Wikipedia and elsewhere who do).

The last thing I'll say is that another reason you'll be told to just use the built in sort is that it's very common to pre-optimize code, which can lead to more problems down the line. It's rare that you'll need to write your own sorting algorithm, but it can happen.

Answer 2

In practice you call a method or function provided by your computer’s operating system or your languages standard library.

The algorithm used is likely a mixture of different algorithms and designed to minimise average runtime - with “average” meaning the average over arrays that users actually try to sort. Methods that help us looking for a sorted sequence at the start and end of the array which can let you combine two sorted arrays and sort the result in O(n), checking for an array that is sorted with few changes (if you start with an array of n items and change k of them, you can sort the result in O(n + k log k)), possibly checking for small arrays.

Usually sorting will be comparison based, because that allows for a consistent interface.

Plus there is the possibility of partially sorting: You may want to display an array in sorted order, but then you only need to sort the part that is being displayed; quicksort can do that nicely.