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"?

  • $\begingroup$ Not answering your question, but by “databases” do you mean SQL databases? In this case, simply use the standard sorting, it’s likely to do it better than what you can possibly implement. $\endgroup$
    – user114966
    Feb 23 '21 at 11:08
  • $\begingroup$ @Dmitry I have created these databases myself in C. $\endgroup$
    – linker
    Feb 23 '21 at 11:21
  • $\begingroup$ Then you might need to experiment yourself. There isn't an "off the shelf" best algorithm, since we can usually only describe its running time in big-O and not the actual time it would run. But basically, try to implement all of them and check which one runs faster (or use the standard sorting instead, its the better option) $\endgroup$
    – nir shahar
    Feb 23 '21 at 11:33
  • $\begingroup$ @nirshahar it takes a long time, I would guess that since algorithms are something that is widely used that there might be some simple condensed theory or some graph out there. How does negative numbers affect the algorithms? I cannot find a source for this. $\endgroup$
    – linker
    Feb 23 '21 at 12:23
  • 1
    $\begingroup$ Sadly, there isn't a theory for the actual running time of algorithms, since there are too many factors to consider (the code, the compiler, the cpu, storage, etc). This is why we use big-O instead. However there are algorithms that usually are faster in practice than others. I dont really know the difference between them, but I think that mergesort is one of them. Try to find other algorithms and see if they suit your needs $\endgroup$
    – nir shahar
    Feb 23 '21 at 12:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.