Introduction
We have often felt the need to sort our data. Whether it be it a list, array, or any collection, the very first problem we face is choosing the right sorting algorithm. Since there are many different sorting techniques/algorithms and some algorithms are better than the others, there is no best sorting algorithm, it depends on the data/situation. Before looking at when to use each sorting algorithm, let's look at the factors which help us to determine a good sorting algorithm.
Time/Time Complexity
This factor helps us to know how much fast is an algorithm? And this factor has 3 major scenarios, firstly is when the data is sorted beforehand, which means no swaps are needed, it only checks the order of the data. This is known as a best-case scenario. The second scenario, the worst-case scenario, is when the algorithm needs to perform maximum swapping in order to sort the data. The last scenario is when the number of swapping lies between 0 to maximum, or in other words, the most common scenario is termed as an average case scenario.
Space/Space Complexity
It tells us about how much extra space does an algorithm takes? If the algorithm requires no space then it is a good algorithm and vice versa.
Swap Efficient
Most of the time, there's a cost associated with swapping the elements. If the swapping is expensive, then an algorithm that does minimum swapping is declared as an efficient algorithm.
Preserves Data Integrity
This factor tells us whether the order of the same elements is maintained or not? If there are two similar elements in a collection, then the algorithm which preserves the order of the elements is a good algorithm. For example, in [5, 2, 7, 2, 1] all sorting algorithms will result in [1, 2, 2, 5, 7], but those algorithms that maintain the 2's order are stable algorithms. In order words, let's mark the similar elements [5, 2(A), 7, 2(B), 1]. Now the algorithm that gives [1, 2(B), 2(A), 5, 7] is an unstable algorithm.
RAM Friendly
Sometimes the data is so huge that it cannot be loaded into RAM. In such a case, those algorithms which work on data stored on a hard drive are considered RAM-friendly algorithms.
There are a
lot of sorting algorithms out there, but I will consider the most commonly-used/easy-to-implement algorithms, namely selection sort, insertion sort, merge sort, and quick sort. So, I have come up with a decision tree in order to solve the problem of choosing the right sorting algorithm with respect to data/situations (generally).