There are many more sorting algorithms in existence, but most are variations of the ones above. The one that is probably missing in the discussion is “heapsort”, which I will bring up briefly in the chapter on trees. All these sorting algorithms are “comparison sorts”, which means that they are based on comparisons between elements. The best time complexity for the algorithms I showed is O(n*log(n)), which held for merge sort and quicksort. It can be proved mathematically that this is, in fact, optimal: for comparison sorts no better big-O time complexity can be achieved. Naturally, that does not mean that there is no difference between the algorithms which achieve this optimal big-O. Other factors might influence their efficiency in terms of time and memory.
In this chapter, you learned about: